快排QuickSort

**1、算法思想：** 一趟快速排序的算法是： 1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换； 5）、重复第3、4步，直到I=J； **2、代码实现：** 注意： ~~~ if (a.length > 0) { // 查看数组是否为空             quickSort(a, 0, a.length - 1);         } ~~~ ~~~ private static void quickSort(int[] list, int low, int high) { if (low < high) {// 不是while，否则死循环 int middle = partition(list, low, high); // 将list数组进行一分为二 quickSort(list, low, middle - 1); // 对低字表进行递归排序 quickSort(list, middle + 1, high); // 对高字表进行递归排序 } } private static int partition(int[] arr, int low, int high) { int tmp = arr[low]; // 数组的第一个元素作为基准,用temp临时存储 while (low < high) {// 从区间两端交替向中间扫描，直至low=high为止 while (low < high && arr[high] >= tmp) {// high向前搜索,直到找到第一个比temp小的元素 high--; } arr[low] = arr[high]; // 比temp小的(high)移到低端 while (low < high && arr[low] <= tmp) {// low下标增至第一个比temp大的元素 low++; }// while终止说明arr[low]>temp arr[high] = arr[low]; // 比temp大的(low)移到高端 } // 当low == high，完成一趟快速排序，此时low位相当于空，等待基准temp补上 arr[low] = tmp; // 基准记录已被最后定位 return low; // 返回基准的位置【下标】<基准最终位置> } ~~~ **3、算法分析** 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。 **（1）最坏时间复杂度** 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。 因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值： Cmax = 1+2+3+……(n-1)=n(n-1)/2=O(n2) 如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。 **（2）最好时间复杂度** 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数： 0(nlgn) 注意： 用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。 （3）基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键。 **①"三者取中"的规则** "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。 **②取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准** 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。 注意： 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。 （4）平均时间复杂度 尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。 （5）空间复杂度 快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。 （6）稳定性 快速排序是非稳定的，例如[2，2，1]。 **4、算法改进** 在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。 源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/QuickSort.java)