为什么说快速排序是最快排序算法快速排序算法 _小知识

迅速排序算法（为什么说迅速排序是最快排序算法）托尼·霍尔在前苏联莫斯科国立大学做拜访学生时，为懂得决俄文排序问题，他首先尝试了插入排序，但是由于不满插入排序的效力，他想出了迅速排序的办法。大神的世界就是自己给自己创造工具。高德纳为了写书而开发了印刷行业最好的排版软件，牛顿为懂得决加速度等问题而创造了微积分。但是霍尔当时没有控制支撑递归的编程语言，所以一直没有实现该算法。直到后来回到英国，学习了ALGOL(支撑递归)语言，他才把自己的想法付诸实践，而且发明竟然比希尔排序还要快。

文章插图
迅速排序算法（为什么说迅速排序是最快排序算法）
也许有的读写还想追问，有没有比迅速排序更快的办法了呢？没有了，这个可以从数学角度证明。如果有人非要说有更快的方法，那他就是在挑衅数学，这和信任永动机的人挑衅热力学定律没有实质上的差别。
迅速排序，充足应用了分治(divide and conquer)的思想，其核心思想就是少做无用功。
根本思想
2.1 迅速排序的一般进程
迅速排序的一般进程是，随机选取数组中的一个值，作为比拟尺度，一般称之为枢值(Pivot) 。然后把全部数组中小于枢值的数据分到一个组，把大于枢值的数据分到另一个组，等于枢值的数据分到哪个组都可以。分成两组后，自然不会用其他排序对小数组进行排序，而是反复以上的步骤，把小的数组再细分。这样全部数组就由1个数组变成2个数组，再变成4个数组，再变成8个数组，到最后分无可分，简略比拟一下，全部数组就变得有序了。
简略描写一下：
选择枢值。也就是选择一个数据作为标杆。选择枢值其实是最主要的一个步骤，比拟推举的办法是，选择数组中第一个、中间以及最后一个数据中的中值。
分组操作。把大于枢值的数据放到枢值右边，把小于枢值的数据放到左边。与枢值相等的数据放到哪边无所谓。
递归。对左右两边的数据进行枢值选取和分组操作。递归的停滞条件是细分数组数据个数为0或者1 。
来看一张稍微庞杂一点的图，图中暗影部分的数据就是各个阶段的枢值。
为什么说迅速排序是最快排序算法？
From Wikipedia
枢值选取方法和分组操作是迅速排序的核心，常见的有两种计划，即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，则枢值
Pivot = A[(lo + hi) / 2]

文章插图
当然，为了避免整数溢出问题，一般写成
Pivot = A[lo + (hi - 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进行如上操作，发明已经完成排序。
老规则，上伪码：
为什么说迅速排序是最快排序算法？
2.4 其他分组计划
此外，《算法导论》中还提到随机化，也就是随机的选择枢值，可能你不信，很多排序算法都会用到随机化这个概念，因为很多时候，随机化带来的成果往往意想不到的好。这里暂不赘述，有机遇单独讲一讲。Sedgewick推举一种选取枢值的办法被称为三数取中(median-of-three)，即从数组第一个数据、正中间数据以及最后一个数据中选取中间值为枢值。三数取中的升级版本也被称为ninther，不妨定义函数median-of-three (Mo3)：