2.3-快速排序-20200726
2.3 快速排序
快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多 。 快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助战），且将长度为 N 的数组排序所需的时间和NlgN成正比 。我们已经学习过的排序算法都无法将这两个优点结合起来 。 另外，快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。 它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能 。 已经有无数例子显示许多种错误都能致使它在实际中的性能只有平方级别 。
2.3.1 基本算法
快速排序是一种分治的排序算法 。 它将一个数组分成两个子数组，将两部分独立地排序 。 快速排序和归并排序是互补的 ： 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。 在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后 。在归并排序中，一个数组被等分为两半； 在快速排序中，切分（ partition ）的位置取决于数组的内容。
快速排序递归地将子数组 a [lo … hi ］ 排序，先用 partition（） 方法将 a[ j ］ 放到一个合适位置，然后再用递归调用将其他位置的元素排序 。
该方法的关键在于切分，这个过程使得数组满足下面三个条件：
★ 对于某个 j, a [ j ］ 已经排定；
★ a[ lo]到 a[j-1］中 的所有元素都不大于 a [ j ];
★ a [j+l ］ 到 a [hi ］ 中的所有元素都不小a[j]。
因为切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序 ：如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素）、切分元素和右子数组（有序且没有任何元素小于切分元素）组成的结果数组也一定是有序的 。
要完成这个实现，需要实现切分方法 。 一般策略是先随意地取 a [lo ］ 作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。 这两个元素显然是没有排定的，因此我们交换它们的位置。 如此继续．我们就可以保证左指针i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都
不小于切分元素 。 当两个指针相遇时，我们只需要将切分元素 a [lo ］ 和左子数组最右侧的元素（ a [j J ）交换然后返回 j 即可 。
2.3.1.1 原地切分
如果使用一个辅助数组，我们可以很容易实现切分，但将切分后的数组复制回去的开销也许会使我们得不偿失 。
2.3.1.2 别越界
如果切分元素是数组中最小或最大的那个元素，就要小心别让扫描指针跑出数组的边界。partition( )实现可进行明确 的检测来预防这种情况 。 测试条件（ j==lo ）是冗余的 ，因为切分元素就是 a[lo］ ，它不可能比自己小 。 数组右端也有相同的情况。
2.3.1.3 保持随机性
数组元素的顺序是被打乱过的 。 因为 对所有的子数组都一视同仁，它的所有子数组也都是随机排序的 。 这对于预测算法的运行时间很重要 。 保持随机性的另一种方法是在 partition()中随机选择一个切分元素 。
2.3.1.4 终止循环
有经验的程序员都知道保证循环结束需要格外小心，快速排序的切分循环也不例外 。 正确地检测指针是否越界需要一点技巧，并不像看上去那么容易 。 一个最常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。
2.3.1.5 处理切分元素值有重复的情况
左侧扫描最好是在遇到大于等于切分元素值的元素时停下，右侧扫描则是遇到小于等于切分元素值的元素时停下 。 尽管这样可能会不必要地将一些等值的元素交换，但在某些典型应用中，它能够避免算法的运行时间变为平方级别。
2.3.1.6 终止递归
有经验的程序员还知道保证递归总是能够结束也是需要小心的，快速排序也不例外 。 例如，实现快速排序时一个常见的错误就是不能保证将切分元素放人正确的位置，从而导致程序在切分元素正好是子数组的最大或是最小元素时陷入了无限的递归循环之中 。
2.3.2 性能特点
快速排序切分方法的内循环会用一个递增的索引将数组元素 和一个定值比较 。 这种简洁性也是快速排序的一个优点，很难想象排序算法中还能有比这更短小的内循环了 。 例如，归并排序和希尔排序一般都比快速排序慢，其原因就是它们还在内循环中移动数据 。
快速排序另一个速度优势在于它的比较次数很少 。 排序效率最终还是依赖切分数组的效果，而这依赖于切分元素的值 。 **切分将一个较大的随机数组分成两个随机子数组，而实际上这种分割可能发生在数组的任意位置（**对于元素不重复的数组而言）。
快速排序的最好情况是每次都正好能将数组对半分 。 在这种情况下快速排序所用的比较次数正好满足分治递归的 Cn=2C(n/2)＋N 公式 。2C(N/2)表示将两个子数组排序的成本， N 表示用切分元素和所有数组元素进行比较的成本 。 由归并排序的命题 F 的证明可知，这个递归公式的解 Cn~NlgN。 尽管事情并不总会这么顺利，但 平均而言切分元素都能落在数组的中间 。 将每个切分位置的概率都考虑进去只会使递归更加复杂 、 更难解决，但最终结果还是类似的 。 我们对快速排序的信心来自于这个结论的证明 。
在实际应用中，当数组元素可能重复时，精确的分析会相当复杂，但不难证明即使存在重复的元素，平均比较次数也不会大于 Cn。
尽管快速排序有很多优点，它的基本实现仍有一个潜在的缺点：在切分不平衡时这个程序可能会极为低效 。 例如，如果第一次从最小的元素切分，第二次从第二小的元素切分， 如此这般， 每次调用只会移除一个元素 。 这会导致一个大子数组需要切分很多次。 我们要在快速排序前将数组随机排序的主要原因就是要避免这种情况 。 它能够使产生糟糕的切分的可能性降到极低，我们就无需为此担心了 。
总的来说，可以肯定的是对于大小为 N 的数组，运行时间在1. 39NlgN 的某个常数因子的范围之内 。 归并排序也能做到这一点，但是快速排序一般会更快（尽管它的比较次数多39% ），因为它移动数据的次数更少。
2.3.3 算法改进
2.3.3.1 切换到插入排序
和大多数递归排序算法一样， 改进快速排序性能的一个简单办法基于以下两点：
★ 对于小数组，快速排序 比插入排序慢 ；
★ 因为递归，快速排序的 sort( )方法在小数组中也会调用自己 。
因此，在排序小数组时应该切换到插入排序 。 简单地改动就可以做到这一点 ：将sort( )中的语句
if (hi <= lo)return;
替换成下面这条语句来对小数组使用插入排序：
if （hi<= lo ＋M）{
Insertion. sort(a, lo,hi )；return; }
转换参数 M 的最佳值是和系统相关的 ， 但是 5～15 之间的任意值在大多数情况下都能令人满意
2.3.3.2 三取样切分
改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组 。 这样做得到的切分更好，但代价是需要计算中位数。 人们发现将取样大小设为 3 并用大小居中的元素切分的效果最好。
2.3.3.3熵最优的排序
一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素 。 这种切分实现起来 比我们目前使用的二分法更复杂。
这段排序代码的切分能够将和切分元素相等的元素归位，这样它们就不会被包含在递归调用处理的子数组之中了 。 对于存在大量重复元素的数组。这种方法 比标准的快速排序的效率高得多。
对于只有若干不同主键的随机数组 ， 归并排序的时间复杂度是线性对数的，而三向切分x快速排序则是线性的 。
给定任意一个待排序的数组，通过统计每个主键值出现的频率就可以计算出它包含的信息量。值得一提的是，可以通过这个信息量得出三向切分的快速排序所需要的比较次数的上下界 。
当所有的主键值均不重复时有 H=lgN （所有主键的概率均为 1/N ），三向切分的最坏情况正是所有主键均不相同 。 当存在重复主键时，它的性能就会比归并排序好得多。更重要的是， 这两个性质一起说明了三向切分是信息量最优的，即对于任意分布的输入，最优的基于比较的算法平均所需的比较次数和三向切分的快速排序平均所需的比较次数相互处于常数因子范围之内。
对于标准的快速排序，随着数组规模的增大其运行时间会趋于平均运行时间，大幅偏离的情况非常罕见，因此可以肯定三向切分的快速排序的运行时间和输入的信息量的 N倍是成正比的 。 在实际应用中这个性质很重要，因为对于包含大量重复元素的数组，它将排序时间从线性对数级降低到了线性级别 。 这和元素的排列顺序没有关系，因为算法会在排序之前将其打乱以避免最坏情况 。 元素的概率分布决定了信息量的大小，没有基于比较的排序算法能够用少于信息量决定的比较次数完成排序。 这种对重复元素的适应性使得三向切分的快速排序成为排序库函数的最佳算法选择一一需要将包含大量重复元素的数组排序的用例很常见 。
经过精心调优的快速排序在绝大多数计算机上的绝大多数应用中都会比其他基于比较的排序算法更快。 快速排序在今天的计算机业界中的广泛应用正是因为我们讨论过的数学模型说明了它在实际应用中 比其他方法的性能更好，而近几十年的大量实验和经验也证明了这个结论 。