快速排序（Quick Sort）

• • • 算法描述
    • 动图演示
    • 代码实现
    • 算法分析

快速排序使用分治法来把一个串（list）分成两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为“基准”（pivot）;
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放到基准值的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

注意：此动图演示的 数据移动的顺序 和下列代码是一致的，标黄意味着设为temp值，当前位置待放入相应数据；
特别注意：这里标黄的位置是占指针索引的，相当于空出位置给待放入的数据，temp数据会在分区结束时放到最后一个数据移动的前的位置，相当于此次分区返回的mid的位置。
此图演示的 数据检索的顺序 和下列代码是不一致的，
标紫意味着满足while循环的条件，此时指针移动
标绿意味着不满足while循环的条件，此时数据移动
建议：在草纸上写一个数组，按演示代码的逻辑自己走一遍，彻底理解算法的逻辑

public static void main(String[] args){
  int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}；
  //只需要修改成对应的方法名就可以了
  quickSort(array);
  System.out.println(Arrays.toString(array));
}

 public static void quickSort(int[] array){
 	quickSort(array,0,array.length - 1);
 }
 private static void quickSort(int[] array,int left,int right){
 	if(array == null || left >= reght || array.length <= 1){
 		return;
 	}
 	int mid = partition(array,left,right);
 	quickSort(array,left,mid);
 	quickSort(array,mid + 1,right);
 }
 private static int partition(int[] array,int left,int right){
 	int temp = array[left];
 	while(right > left){
 		//先判断基准数和后面的数依次比较
 		while(temp <= array[right] && left < right){
 			--right;
 		}
 		//当基准数大于了array[left]，则填坑
 		if(left < right){
 			array[left] = array[right];
 			++left;
 		}
 		//现在是array[right]需要填坑了
 		while( temp >= array[left] && left < right){
 			++left;
 		}
 		if(left < right){
 			array[right] = array[left];
 			--right;
 		}
 	}
 	array[left] = temp;
 	return left;
 }