快速排序(为什么快速排序是最快的排序算法)前苏联莫斯科国立大学访问学生Tony Hall第一次尝试插入排序解决俄语排序问题时，因为对插入排序的效率不满意，想出了快速排序的方法。大神的世界就是为自己发明工具。Gartner开发了印刷业中最好的写书排版软件，而牛顿发明了微积分来解决加速度等问题。但是，霍尔当时并没有掌握支持递归的编程语言，所以一直没有实现算法。直到回到英国学习ALGOL(递归支持)语言，他才把自己的想法付诸实践，发现Bisir排名甚至更快。

快速排序(为什么快速排序是最快的排序算法)。

可能有些读者想问，有没有比快速排序更快的方法？不，这可以用数学证明。如果有人坚持认为有更快的方法，那他就是在挑战数学，这和那些相信永动机挑战热力学定律的人没有本质区别。

快速排序充分利用了分而治之的思想，其核心思想是少做、不做。

基本思路【/br/】2.1快速排序的一般过程【/br/】快速排序的一般过程是在数组中随机选择一个值作为比较标准，一般称为Pivot。然后，将整个数组中小于透视值的数据分成一组，大于透视值的数据分成另一组，等于透视值的数据可以分成任意组。分成两组后，小数组自然不会按其他排序，而是通过重复上述步骤进行细分。这样，整个阵列就会从一个阵列变成两个阵列，再变成四个阵列，再变成八个阵列，最后就密不可分了。简单对比后，整个阵列会变得有序。

简单描述一下:

选择轴心值。也就是选择一个数据作为基准。选择枢轴值实际上是最重要的一步。推荐的方法是选择数组中第一个、中间和最后一个数据的中值。
分组操作。将大于透视值的数据放在右边，将小于透视值的数据放在左边。与透视值相等的数据放在哪里并不重要。
递归。对左右数据执行透视值选择和分组操作。递归的停止条件是细分数组数据的个数为0或1。
我们来看一个稍微复杂一点的数字。图中的阴影数据是每个阶段的轴心值。

为什么快速排序是最快的排序算法？
来自维基百科

透视表值选择和分组操作是快速排序的核心。有两种常见的方案，即Lomuto和Hoare分组方案。

2.2 Lomuto分组方案
最简单也是最常见的分组方式是Lomuto分组方案，直接选择最后一个元素作为枢纽值。这种方案最明显的缺点是，当一个数组已经排序或者数组中的所有数字都相同时，会出现最差的排序情况，即复杂度为O(n)。

不要看1，2，3，4，5的数组。该方案首先选择5作为枢纽值，然后第一次分组后，左边只有1、2、3、4四个数字，右边没有数字。如果第二次选择4作为枢纽值，结果还是一样，所以每次分组只能让一个数有序，效率自然退化为O(n)。

直接伪码:

为什么快速排序是最快的排序算法？
2.3 Hoare分组方案
另一种方法是Hoare分组方案，通过一定的方法选择一个枢纽值，一般选择数组中间的值。如果数组A的第一个元素和最后一个元素的下标分别是lo和hi，那么透视值将是。

枢轴= A[(lo + hi) / 2]

当然，为了避免整数溢出，一般写成。

枢轴= A[lo +(高-低)/ 2]

有机会再说整数溢出。思路是从数组的左右两端开始，从左端到右端找到大于等于枢轴值的第一个数据，记录索引I，从右端到左端找到小于等于枢轴值的第一个数据，记录索引j，然后交换A[i]和A[j]。然后继续上面的操作，直到I大于等于j，这样原始数组就分成了两个数组，左边一个小于透视值，右边一个大于等于透视值，然后对子数组重复上面的操作。

以数组4、5、3、2和1为例:

选择3作为枢轴值，发现左端数据4大于枢轴值，右端数据1小于枢轴值。交换数据得到1，5，3，2和4。
继续向内扫描数据，发现需要交换5和2，从而得到1、2、3、4和5。
继续对两个子阵列1、5和4、5执行上述操作。
像往常一样，添加伪代码:

为什么快速排序是最快的排序算法？【/br/】2.4其他分组方案【/br/】此外，《算法导论》中也提到了随机化，即随机选择枢纽值。你可能不信，但是很多排序算法都会用到随机化的概念，因为在很多情况下，随机化往往会带来意想不到的结果。这里暂时不赘述，但有机会单独谈谈。Sedgewick推荐的一种选择枢纽值的方法叫做三中值，即从数组的第一个数据、中间数据和最后几百个网站中选择中值作为枢纽值。数字三的升级版本也称为ninther，因此您可能希望定义函数三的中位数(Mo3):

Mo3(A) =中位数(A[1]，A[n/2]，A[n])

宁瑟(a) =中位数(mo3(a的第一个⅓)，mo3(a的中间⅓)，mo3(a的最后一个⅓))

即取数组的前三分之一求中值，然后取数组的中间三分之一求中值，再取数组的最后三分之一求中值，最后在三个中值中选择中值。

复杂度
3.1时间复杂度
对于有序数组或数据相等的数组，快速排序为O(n)。有很多方法可以优化这种情况。例如，您可以尝试将数据分为三组，即一组大于透视值，一组等于透视值，一组小于透视值。原因很好理解，在此不再赘述。您也可以评估数据的数量。对于较少的数据，根本不需要使用快速排序，但是可以直接使用选择性排序或Hill排序。

快速排序的平均复杂度为O(n*log n)，合并排序和堆排序的复杂度也为O(n*log n)，那么为什么一般说快速排序是最快的排序算法呢？其实看过我之前关于复杂度的文章的读者应该知道，对于复杂度为O(C*n*log n)的算法，Best Network的复杂度为O(n*log n)，其中C为常数。快速排序之所以最快，是因为它的常数c比较小，而在具体应用中，快速排序的性能往往更好。

3.2空之间的复杂度/
快速排序的空之间的复杂度与具体实现有关。Sedgewick描述的一种方案，针对原地排序，首先通过递归对元素最少的包进行排序，最多需要/其他不在位排序实现，空之间的复杂度为O(n)。

其实我们也可以从另一个角度去理解快速排序的空之间的复杂性。快速排序的递归过程可以用二叉树表示，因此调用栈的层次与二叉树的深度一致，最佳情况下树的深度为O(log n)，即空之间的复杂度为O(log n)。最差的情况发生在二叉树退化成深度为O(n)的单链时，空之间的复杂度为O(n)。

3.3稳定性和实际性能
快速排序也是一种不稳定的排序算法。

衡量算法的性能，简单看插入排序、希尔排序、快速排序的效率。以耗时的1万个随机数排序为例:

为什么快速排序是最快的排序算法？
显然，快速排序只需要希尔排序时间的一半。想要获取源代码，在后台回复“快速排序”即可获取源代码。

总结分析【/br/】快速排序的整体思路很简单，就是按照一定的标准(枢纽值)，先把369等的数据分开，然后继续把369等的数据在小范围内划分，直到没有分离为止。也就是说，每个数据都找到了自己的位置。快速排序中空的复杂度比Hill排序要大得多，这再次说明了计算机科学中有一个取舍问题，空用于时间。

关于快速排序枢纽值的选择，方法数不胜数，表现参差不齐。但只要遵循核心思想，分拣速度会有质的提升。从代码实现的角度来看，快速排序的实现只需要10多行代码。可见，好事往往极其简单。如果你把事情复杂化了，不妨停下来想一想，做事的方式是否有问题。

在许多情况下，我们应该用同样的方式做事。我们要学会分而治之，按照一定的标准无限细分大问题，到了谷底，只需要做几件事就能完成一个大目标。就像一个公司，不同的人被分配到不同的岗位，然后各司其职，就能创造出一个伟大的公司。