快速排序基本思想超详细一看就懂

快速排序基本思想超详细一看就懂快速排序算法是一种非常高效的排序算法，它采用“分而治之”的思想，将大的拆分为小的，小的拆分为更小的。如果说，希尔排序是直接插入排序的升级（插入类），堆排序是简单选择排序的升级（选择类），那么快速排序等于前面我们认为最慢的冒泡排序的升级（交换类）。快速排序算法是图灵获奖者Tony

Hoare

设计出来的，他在形式化方法理论以及ALGOL60编程语言发明中有卓越的贡献，是上世纪最伟大的计算机科学家之一。而快速排序算法只是他众多贡献中的一个小发明而已。其原理如下：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的记录均比后一部分的所有记录小（有序）；然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列的所有记录均有序为止。图解快排算法思想结合图例，快速排序的算法步骤大致如下：1、我们有一个数组：[2,1,7,9,5,8]2、分割1：按照快速排序的思想，首先把数组筛选成较小和较大的两个子数组。选择基准值7，将原数组分割为两个子数组：[2,1,5]和[7,9,8]3、分割2：针对两个子数组：[2,1,5]和[7,9,8]，在较小的子数组里选2作为基准值，在较大的子数组里选8作为基准值，继续分割子数组。基准值2，[2,1,5]分割为：[1]和[2,5]基准值8，[9,8]分割为：[8]和[9]4、分割3：继续将元素个数大于1的子数组进行划分，当所有子数组里的元素个数都为1的时候，原始数组也被排好序了。基准值2，[2,5]分割为：[2]和[5]基准值8，[9,8]分割为：[8]和[9]5、分割结果，所有子数组的元素个数都为1，得到结果数组：我们从上面可以总结出规律，在实行分治过程中，如何选择基准值并拆分数组是难点。拆分算法是整个快速排序中的核心，快速排序拥有非常多的拆分方式，其中广泛使用的是单指针遍历法与双指针遍历法。篇幅所限，我们这里对面试常常问的双指针遍历算法进行图解剖析。快速排序算法之双指针遍历实现图解快速排序算法之双指针遍历实现图解：1、首先，我们得到一个初始数组：[2,1,7,9,5,8]2、进行第1次枢轴挑选，得到枢轴元素下标=13、根据第1次枢轴挑选结果，进行递归处理4、递归1：左边数组5、递归1：右边数组6、进行第2次枢轴挑选，得到枢轴元素下标=37、根据第2次枢轴挑选结果，进行递归处理8、递归2：右边数组9、递归2：左边数组10、进行第3次枢轴挑选，得到枢轴元素下标=511、此时，我们完成对数组的快速排序，得到顺序数组输出：[1,2,5,7,8,9]快速排序算法之双指针遍历实现代码下面是快速排序的算法实现：publicclassQuickSort{publicstaticvoidmain(String[]args){int[]array={2,1,7,9,5,8};QSort(array,0,5);System.out.println(Arrays.toString(array));}

privatestaticvoidQSort(int[]nums,intlow,inthigh){intpivot;if(low>=high){return;}//难点也是核心，partition函数工作内容：选取某个中枢元素（枢轴,pivot），然后想办法将它放到某一位置，//使得它左边的值都小于它，右边的值都大于它。pivot=partition(nums,low,high);//分解为更小的问题，递归QSort(nums,low,pivot-1);QSort(nums,pivot+1,high);}

/***<p>*1、交换顺序表nums的记录，使得枢轴到位，并返回所在位置*2、确保枢轴左边元素<枢轴，枢轴右边元素>枢轴*3、选取枢轴策略就是元素的中位数的下标。*/privatestaticintpartition(int[]nums,intlow,inthigh){intpivotKey=nums[low];while(low<high){while(low<high&&nums[high]>=pivotKey){//findouttheelementwhichissmallerthenpivotKeyhigh--;}

//一次遍历，找到比基准值更小的元素并排序到前面swap(nums,low,high);while(low<high&&nums[low]<=pivotKey){//findouttheelementwhichisbiggerthenpivotKeylow++;}

//一次遍历，找到比基准值更大的元素并排序到后面swap(nums,low,high);}returnlow;}

staticvoidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}}输出：[1,2,5,7,8,9]快排复杂度分析我们来分析下快速排序算法的性能：快速排序的时间复杂度取决于快速排序递归的深度，在最优情况下，快速排序算法的时间复杂度为O(nlogn)。在最坏情况下，待排序序列为正序或者逆序，每次划分只得到一个比上次少一个记录的子序列（另一个为空），最终时间复杂度为O(n^2)。由数学归纳法，其数量级为O(nlogn)。快速排序的空间复杂度主要是递归造成的栈空间的使用，最好情况，递归树的深度为logn，那么它的空间复杂度也是O(logn)。最坏情况，要进行n-1次递归调用，那么空间复杂度就是O(n)。平均情况，空间复杂度为O(logn)。由于关键字的比较和交换是跳跃进行的，因此快速排序是不稳定的排序方法。总结

递归排序算法，还是有不少值得优化的地方：1、优化选取枢轴：采用三数取中法（median-of-three），即取是哪个关键字先进行排序，将中间数作为枢轴，一般使用左端、右端和中间三个数，或者随机选取。或者采用九数取中（medina-of-nine），从数组中三次取样每次三个，基于样品取中数，然后从三个中数再取中数作为枢轴。2、优化不必要的交换3、优化小数组时的排序方案如果