本文转载自微信公众号《内测学习JAVA》，作者Silently9527。转载本文请联系贝塔学习JAVA公众号。本文已收录在Github仓库https://github.com/silently9527/JavaCore程序员常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin完全开源淘客项目：https://github.com/silently9527/mall-coupons-server前言快速排序可以说是应用最广泛的排序算法，主要特点是基于就地排序（不需要使用辅助数组，节省空间）；事实上，快速排序用于长度为N的数组，时间复杂度为NlogN；其他的排序算法在之前的文章中也有讨论，但是都没有能够结合这两个特点。快速排序思想快速排序也是一种分而治之的排序算法，将数组分成两个子数组，然后对子数组进行递归排序，保证整个数组有序。算法思想：随机选择一个切分元素，通常是选择数组的第一个元素从数组左侧开始扫描找到大于等于切分元素的值，从数组右侧开始扫描到找到小于等于分割元素Value的值，交换这两个值并循环这个过程，直到左右指针相遇，这样安排一个元素，保证左边的值split元素都小于它的值，右边的元素都大于它的值Recursion这个过程最终保证了整个数组排序算法的实现。根据快速排序算法的思路，我们可以写出第一版的实现：publicclassQuickSortimplementsSortTemplate{@Overridepublicvoidsort(Comparable[]array){quickSort(array,0,array.length-1);}privatevoidquickSort(Comparable[]array,intlo,inthi){if(lo>=hi){return;}intpartition=partition(array,lo,hi);quickSort(array,lo,partition-1);quickSort(array,partition+1,hi);}privateintpartition(Comparable[]array,intlo,inthi){inti=lo,j=hi+1;Comparableel=array[lo];while(true){while(less(array[++i],el)){if(i==hi){break;}}while(less(el,array[--j])){if(j==lo){break;}}if(i>=j){break;}exch(array,i,j);}exch(array,lo,j);returnj;}}这段代码是快速排序的常规实现，考虑到最坏的情况，如果需要排序的数组是已经订购[1,2,3,4,5,6,7,8]。快速排序的过程如图所示：对于一个长度为N的数组，在最坏情况下，需要递归N次-1次，所以时间复杂度为O(n2)。为了避免这种情况，我们来看看如何改进算法来保证随机性。为了避免最坏的情况，有两种方法。第一种是在对数组排序之前随机打乱数组；二是随机取partition方法中的分割元素元素，而不是固定取第一个，简单实现：privateintpartition(Comparable[]array,intlo,inthi){inti=lo,j=hi+1;intrandom=newRandom().nextInt(hi-lo)+lo;exch(数组,lo,随机);Comparableel=array[lo];while(true){while(less(array[++i],el)){if(i==hi){break;}}while(少（el，数组[--j]））{if（j==lo）{break；}}if（i>=j）{break；}exch（数组，i，j）；}exch（数组，lo,j);returnj;}切换到插入排序与合并排序相同。对于小数组，直接切换到插入排序privatevoidquickSort(Comparable[]array,intlo,inthi){if(lo>=hi){return;}if(hi-lo<5){//测试，切换到插入排序如果小于5insertionSort(array,lo,hi);return;}intpartition=partition(array,lo,hi);quickSort(array,lo,partition-1);quickSort(array,partition+1,hi);}//插入排序privatevoidinsertionSort(Comparable[]array,intlo,inthi){for(inti=lo;i<=hi;i++){for(intj=i;j>lo&&less(array[j],array[j-1]);j--){exch(array,j,j-1);}}}三路切分当我们需要排序的数组中有很多重复元素时，我们实现的快速排序递归的时候会遇到很多重复的子数组，我们的算法还是会把它们切分。这里有很大的改进空间思路是随机选择一个切分元素（el），然后将数组切换为大于、等于、小于三部分。一次递归可以把所有的值都排列成等于分割元素；维护一个指针lt，gt，使得a[lo..lt-1]小于切分元素，a[gt+1..hi]大于切分元素；初始化变量：lt=lo,i=lo+1,gt=hiifa[i]
