快速排序

快速排序（Quicksort）是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码演示

        /**
	   * 划分数组，根据基数，将比基数小的值放在基数左边，比基数大的值放在右边
	   * @param arr
	   * @param start
	   * @param end
	   */
	  public static int partition(int []arr,int start,int end) {
		  int basalVal = arr[start];//基数
		  int  i = start;//从左往右扫描
		  int j = end;//从右往左扫描
		  
		  //循环交换，将比基数大的值和比基数小的值，位置调换，确保比基数小的值在左边，大的值在右边
		  //最终的位置如下：
		  //arr[start...j-1] arr[j]  arr[j+1...end]
		  //其中arr[j]为基数，arr[start...j-1]为比基数小的值,arr[j+1...end]为比基数大的值
		  while(true) {
			  
			  //第一个数为基数 所以i从第二个数开始比较,所以用了++i
			  while(arr[++i]<basalVal) {//若是左边值比基数小，则接着循环，直到找到比基数大的值
				  if(i==end) {//从左往右 若是遍历到最后则跳出循环
					 break;
				  }
				  
			  }
			  //从右边第一个数(即数组最后一个)开始比较
			  while(arr[j]>basalVal) {//若是右边边值比基数大，则接着循环，直到找到比基数小的值
				  j--;
				  if(j==start) {//从右往左 若是遍历到最后则跳出循环
					  break;
				  }
			  }
			  
			//左右扫描产生了交叉，此时说明比较已结束，由于和j相关扫描是找小于基数的值，所以小于等于j的位置的值均为比基数小的值，大于j的均为比基数大的值
			  if(i>=j) {
				  break;
			  }
			  //交换位置
			  exch(arr, i, j);
			  
		  }
		  
		  //比较结束，将基数置于上面临界处即i,j交叉点，
		  exch(arr, start, j);
		  
		  return j;//临界点
	  }
	  
	  
	  /**
	   * 交换位置
	   * @param arr
	   * @param i
	   * @param j
	   */
	  public static void exch(int [] arr,int i,int j) {
		  int temp;
		  temp = arr[i];
		  arr[i] = arr[j];
		  arr[j] = temp;
	  }
	  
	  /**
	   * 排序
	   * @param arr
	   * @param start
	   * @param end
	   */
	  public static void quickSort(int []arr,int start,int end) {
		  if(start>=end) {
			  return ;
		  }
		  
		 int j =  partition(arr, start, end);
		 
		 //分组再排序,递归调用
		 quickSort(arr, start, j-1);//左边数组 a[start...j-1]
		 
		 quickSort(arr, j+1, end);//右边数组a[j+1...end]
		  
		  
		  
	  }
	  

Java 快速排序

原文：https://www.cnblogs.com/xiaoweiday/p/12555551.html