快速排序(为什么快速排序是最快的排序算法)前苏联莫斯科国立大学访问学生Tony Hall为了解决俄语排序问题，首先尝试了插入排序，但是因为对插入排序的效率不满意，所以想出了快速排序的方法。大神的世界就是给自己发明工具。Gartner开发了印刷业最好的写书排版软件，牛顿发明了求解加速度等问题的微积分。但是霍尔当时并没有掌握支持递归的编程语言，所以一直没有实现算法。他直到回到英国，学习了ALGOL(递归支持)语言，才把自己的想法付诸实践，发现Bisir排名更快。
快速排序(为什么快速排序是最快的排序算法)
可能有些读者想问，有没有比快速排序更快的方法？不，这个可以用数学证明。如果有人坚持说有更快的方法，那他是在挑战数学，本质上和那些相信永动机挑战热力学定律的人是一样的。
快速排序充分利用了分而治之的思想，其核心思想是少做无用的工作。
基本思想
2.1快速排序的一般过程
快速排序的一般过程是在数组中随机选择一个值作为比较标准，一般称为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，那么枢轴值是
Baxter。
Pivot = A[(lo + hi) / 2]
当然，为了避免整数溢出，一般写成
Pivot = A[lo+(hi-lo)best net/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
旧规则，伪代码:
为什么快速排序是最快的排序算法？
2.4其他分组方案
此外，《算法导论》也提到了随机化，即随机选择枢纽值。你可能不信，很多排序算法都会用到随机化的概念，因为在很多情况下，随机化往往会带来意想不到的好结果。这里暂不赘述。我有机会单独谈谈。Sedgewick推荐了一种选择枢轴值的方法，称为三中值，即从数组的第一个数据、中间数据和最后一个数据中选择中间值作为枢轴值。三重选择的升级版也叫ninther，所以你可能希望定义三重中值函数(mo3):
Mo3(A) =中位数(A[1]，A[n/2(原创版权www.isoyu.com)]，A[n])
n ther(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)的算法，复杂度为O(n*log n)，其中C为常数。快速排序之所以最快，是因为它的常数c比较小，在具体的应用中，快速排序往往性能更好。
3.2空间复杂度
快速排序的空间复杂度与具体实现有关。Sedgewick描述的一个方案旨在就地排序。首先通过递归对元素最少的分组进行排序，最多需要O(log n)的空间，然后再对另一部分分组数据进行尾部递归或迭代排序，避免了将这种排序操作加入到调用栈中，也就是说可以将调用栈的深度限制在不超过O(log n)，从而保证了空间复杂度。非就地排序的其他实现具有0(n)的空间复杂性。
其实可以从另一个角度理解快速排序的空间复杂性。快速排序的递归过程可以用二叉树表示，所以调用栈的层次与二叉树的深度一致，最佳情况下树的深度为O(log n)，即此时空间复杂度为O(log n)。最差的情况发生在二叉树退化成深度为O(n)，空间复杂度为O(n)的单链时。
3.3稳定性和实际性能
快速排序也是一种不稳定的排序算法。
衡量算法的性能，简单看插入排序、希尔排序、快速排序的效率。以一万个随机数的排序时间为例:
为什么快速排序是最快的排序算法？
显然，快速排序只占希尔排序时间的一半。如果想获取源代码，在后台回复“快速排序”即可获取源代码。
汇总分析
快速排序的整体思路很简单，就是按照一定的标准(枢纽值)，先把369等数据分开，然后继续把369等数据在小范围内分割，直到没有分离为止。也就是每个数据都找到了自己的位置。快速排序的空间复杂度远远大于Hill排序，这再次说明在计算机科学中，处处都有用空间换时间的取舍。
关于快速排序枢纽值的选择，方法众多，性能也参差不齐。但只要遵循它的核心思想，排序的速度就会有质的提高。从代码实现的角度来看，快速排序的实现只需要10行以上的代码。可见，好的事情往往极其简单。如果你把一件事情复杂化了，不妨停下来思考一下，做事的方式是否有问题。
很多时候，做事应该是一样的。要学会分而治之，按照一定的标准无限细分大问题，到了谷底，只需要做几件事就能完成一个大目标。就像一个公司，不同的人被分配到不同的岗位，然后各司其职，就能创造出一个伟大的公司。