快速排序有在大二的《数据结构》课中出现过。

上面这个人的博客讲的非常的好，如果有打算看博客的可以经常关注。

快速排序(Quick Sort)使用分治法策略。

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

快速排序流程：

(1) 从数列中挑出一个基准值。

(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。

(3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序

流程图片：

 

（图片引自上述博客）

上代码：

　

1 public class a_2_8 { 2     public static
      
        void QuickSort(T a[],int left,int right){ 3         if(a==null||left>=right)return ; 4         int mid=partition(a,left,right); 5         QuickSort(a,left,mid-1); 6         QuickSort(a,mid+1,right); 7     } 8  9     public static
       
         int partition(T a[],int left, int right){10         /*1、选择最左边的数字为基准*/11         T base=a[left];12         while(true){13             /*2、找到从右边开始第一个小于base的数的index*/14             while(left
        
         0)--right;15             /*3、将这个数放到左边，因为左边这个数字已经是多余的了*/16             a[left]=a[right];/*4、此时右边的数已经存到了左边，右边是重复存储的位置可等待下面5循环之后覆盖*/17 18             /*5、找到从左边开始第一个大于base的数的index*/19             while(left
         
          <=0)++left;20             /*6、将这个数放到右边，因为左边这个数字已经是多余的了*/21             a[right]=a[left];/*7、此时左边的数已经存到了右边，左边是重复存储的位置可等待下一次循环或者跳出循环时覆盖*/22             if(left>=right)break;/*8、依据7，跳出循环时左边是重复存储的位置，可覆盖*/23         }24         a[left]=base;/*9、此处为将基准数覆盖在重复存储的位置*/25         return left;26     }27 28     public static void main(String args[]){29         Integer integer[]=new Integer[]{30,40,60,10,20,50};30         QuickSort(integer,0,integer.length-1);31         for(Integer i :integer){32             System.out.print(i+" ");33         }34     }35 }
         
        
       
      

注意：注释的9处为什么是

 a[left]=base; 

而不是

 a[right]=base;  

这个问题以前一直没想清楚，现在想清楚了，left的原因是从右边开始扫描，因为是从右边开始扫描，所以注释的4处right位置先成为重复存储的垃圾区域，然后7处将right的垃圾区域覆盖，导致了left成为了垃圾区域，所以在break之后应当将base的值写入left所在的位置。

运行结果如下：

 

上述代码注释基本描述清楚了内容。

前天投的字节跳动的Android实习，然后昨天被pass了，今天突然HR给我改成了面试待安排，我一脸蒙蔽，感觉我是去当炮灰的。不说了，排名26%在牛客网上只能选20%-50%，说了都是泪，要怪就怪自己没好好读书。