数据结构与算法分析读书笔记系列07-排序

我们描述的算法都将是可以互换的。每个算法都将接收一个含有元素的数组和一个包含元素个数的整数。

我们将假设N是传递到我们到排序例程中的元素个数，它已经被检查过，是合法的。按照C的约定，对于所有的排序，数据都将在位置0处开始。

我们还假设“<”和">"运算符存在，它们可以用于将相容的序放到输入中。除赋值运算符外，这两种运算是仅有的允许对输入数据进行的操作。在这些条件下的排序叫做基于比较的排序（comparison-based sorting）。

成员存数的数据的一个逆序（inversion）是指数组中具有性质i<j但A[i] > A[j]的序偶（A[i]，A[j]）。注意，这正好是需要由插入排序（非直接）执行的交换次数。情况总是这样，因为交换两个不按原序排列的相邻元素恰好消除一个逆序，而一个排过序的数组没有逆序。由于算法中还有O（N）项其他的工作，因此插入排序的运行时间是O（I+N），其中I为原始数组中逆序数。于是，若逆序数是O（N），则插入排序以线性时间运行。

我们可以通过计算排列中的平均逆序数而得出插入排序平均运行时间的精确的界。

定理1:N个互异数的数组的平均逆序数是N（N-1）/4。

定理2:通过交换相邻元素进行排序的任何算法平均需要Ω(N²)时间。

这个下界的例子，它不仅对非显式地实施相邻元素的交换的插入排序有效，而且对诸如冒泡排序和选择排序等其他一些简单算法也是有效的。同时这个下界告诉我们，为了使排序算法以亚二次（subquadratic）或o(N²)时间运行，必须执行一些比较，特别要对相距较远的元素进行交换。一个排序算法通过删除逆序得以向前进行，而为了有效地运行，它必须每次交换删除不止一个逆序。

希尔排序（Shellsort）的名称源于它的发明者Donald Shell，正如上节所提到的，它通过比较相距一定间隔的元素来工作各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时也叫做缩小增量排序（diminishing increment sort）。

一趟h_k 排序的作用就是对h_k 个独立的子数组执行一次插入排序。

增量序列的一种流行（但是不好）的选择死使用Shell建议的序列：h_t =N/2和h_k = h_k+1/2。

虽然希尔排序编程简单，但是，其运行时间的分析则完全是另外一回事。希尔排序的运行时间依赖于增量序列的选择，而证明可能相当复杂。

定理：使用希尔增量时希尔排序的最坏运行时间为Θ(N²)。

Hibbard提出一个稍微不同的的增量序列，它在实践中（并且理论上）给出更好的结果。它的增量形如1，3，7,…,2^k-1。虽然这些增量几乎是相同的，但是关键的区别是相邻的增量没有公因子。

定理：使用Hibbard增量的希尔排序的最坏运行时间为Θ(N^3/2)。

使用Hibbard增量的希尔排序平均情形运行时间基于模拟的结果被认为是O(N^5/4)，但是没有人能够证明该结果。

Sedgewick提出了几种增量序列，其最坏情形运行时间（也是可以达到的）为O(N^4/3)。对于这些增量序列的平均运行时间猜测为O(N^7/6)。

关于希尔排序还有几个其他结果，它们需要数论和组合数学中一些艰深的定理而且主要是在理论上有用。希尔排序是算法非常简单且又具有极其复杂的分析的一个好例子。

希尔排序的性能在实践中是完全可以接受的，即使是对于数以万计的N仍是如此。编程的简单特点使得它成为对适度地大量的输入数据经常选用的算法。

正如优先队列那一节提到的，优先队列可以用于花费O(NlogN)时间的排序。基于该想法的算法叫做堆排序（heapsort）。虽然堆排序的大O运行时间优于前面介绍的排序。然而，在实践中它却慢于使用Sedgewick增量序列的希尔排序。

建立N个元素的二叉堆，此时的花费是O（N）时间。然后我执行N次DeleteMin操作。按照顺序，最小的元素先离开该堆。通过将这些元素记录到第二个数组然后再将数组拷贝回来，我们得到N个元素的排序。由于每个DeleteMin花费时间是O（logN），因此总的运行时间是O（NlogN）。

该算法的主要问题在于它使用了一个附加的数组。因此，存储需求增加了一倍。避免使用第二个数组的聪明的做法是利用这样的事实：在每次DeleteMIn之后，堆缩小了1。因此，位于堆中最后的单元可以用来存放刚刚删除的元素。使用这种策略，在最后一次DeleteMin后，该数组将以递减的顺序包含这些元素。

堆排序的分析

第一阶段构建堆最多用到2N次比较。在第二阶段，第 i次DeleteMax最多用到2logi次比较，总数最多为2NlogN-O（N）次比较（设N≥2）。因此，在最坏的情形下，堆排序最多使用2NlogN-O（N）次比较。

经验指出堆排序是一个非常稳定的算法：它平均使用的比较只比最坏情形界值指出的略少。

定理：对于N个互异项的随机排列进行堆排序，所用的比较平均次数为2NlogN - O（NloglogN）。

通过更复杂的论述，可以证明，堆排序总是至少使用NlogN-O（N）次比较，而且存在输入数据能够达到这个界。

归并排序（mergesort）以O(NlogN) 最坏情形运行时间运行，而所使用的比较次数几乎是最优的。它是递归算法一个很好的实例。

这个算法中基本的操作是合并两个已排序的表。因为这两个表是已排序的，所以若将输入放到第三个表中时则该算法可以通过堆输入数据一趟排序来完成。合并两个已排序的表的时间显然是线性的，因为最多进行了N-1次比较，其中N是元素的总数。为了看清这一点，注意每次比较都是把一个元素添加到C中，但最后的比较除外，它至少添加添加两个元素。

归并排序算法描述：如果N = 1，那么只有一个元素需要排序，答案是显然的，否则，递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用上面描述的合并算法再将这两部分合并到一起。

该算法是经典的分治（divide-and-conquer）策略，它将问题分成一些小问题然后递归求解，而治的阶段将分的阶段解得的各个答案修补到一起。

Merge例程是精妙的，如果堆Merge的每个递归调用均局部申明一个临时数组，那么在任一时刻就可能又logN个临时数组处于活动期，这对于小内存的机器则是致命的。另一方面，如果Merge例程动态分配并释放最小量临时内存，那么又malloc占用的时间会很多。由于Merge位于Msort的最后一行，因此在任一时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分；我们将使用与输入数组A相同的部分，这就达到本节末尾描述的改进。图7-10实现了这个Merge例程。

归并排序是用于分析递归例程的经典实例：我们必须给运行时间写出一个递归关系。下述方程给出准确的表示：

T(1) = 1
T(N) = 2T(N/2) +  N

虽然归并排序的运行时间是O(NlogN)，但是它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数据再拷贝回来这样一些附加的工作，其结果严重放慢了排序的速度。这种拷贝可以通过在递归交替层次是审慎地转换A和TmpArray的角色得到避免。归并排序的一种变形也可以非递归地实现，但即使这样，对于重要的内部排序应用而言，人们还是选择快速排序。

正如它的名字标示的，快速排序（quicksort）是在实践中最快的已知排序算法，它的平均运行时间是O(NlogN)。该算法之所以特别快，主要是由于非常精炼和高度优化的内部循环。它的最坏情形的性能为O(N²)，但稍加努力就可避免这种情形。像归并排序一样，快速排序也是一种分治的递归算法。

将数组S排序的基本算法又下列简单的四步组成：

1. 如果S中元素个数是0或者1，则返回。
2. 取S中任意元素v，称之为枢纽元（pivot）。
3. 将S-{v}(S中其余元素)分成两个不相交的集合：S₁ = {x ∈ S-{v} | x ≤ v }和S₂ = {x ∈ S-{v} | x ≥ v}。
4. 返回{quicksort(S₁)}后，继随v,继而quicksort(S₂)。

由于对那些等于枢纽元的元素的处理，第（3）步分割的描述不是惟一的，因此这就成了一个设计上的决策。一部分好的实现方法是将这种情形尽可能有效地处理。

应该知道该算法是成立的，但是不清楚的是，为什么它比归并排序快。如同归并排序那样，快速排序递归地解决两个子问题并需要线性的附加工作(第(3)步)，不过，与归并排序不同，这两个子问题并不保证具有相等的大小，这是个潜在的隐患。快速排序更快的原因在于，第(3)步分割成两组实际上是在适当的位置进行并且非常有效，它的高效弥补了大小不等的递归调用的缺憾而且还有超出。

实现第(2)步和第(3)步有许多方法；这里介绍的方法是大量分析和经验研究的结果，它代表实现快速排序的非常有效的方法。

关于排序的全部讨论，我们已经假设要被排序的元素是一些简单的整数。常常需要通过某个关键字对大型结构进行排序。在这种情况下，实际的解法是让输入数组包含指向结构的指针。我们通过比较指针指向的关键字，并在必要时交换指针来进行排序。这意味着，所有的数据运动基本上就像我们对整数排序那样进行。我们称之为间接排序（indirect sorting）；可以使用这种方法处理我们已经描述过的大部分数据结构。这证明我们关于复杂数据结构处理时不必大量牺牲效率的假设是正确的。

即使在平均情况下，任何只用到比较的任意排序算法都需要进行Ω(NlogN)次比较。这意味着，快速排序在相差一个常数因子的范围内平均是最优的。

特别地，只用到比较的任何排序算法在最坏情况下都需要「log(N!)」次比较并平均需要log(N!)次比较。

决策树(decision tree)是用于证明下界的抽象概念。在我们这里，决策树是一棵二叉树。每个节点表示在元素之间一组可能的排序，它与已经进行的比较一致。比较的结果是树的边。

虽然我们证明了任何只使用比较的一般排序算法在最坏情况下需要运行时间Ω(NlogN)，但是我们要记住在某些特殊情况下以线性时间进行排序仍然是可能的。

一个简单的例子是桶氏排序(bucket sort)。为使桶氏排序能够正常工作，必须要有一些额外的信息。输入数据A₁ ,A₂, …,A_N 必须只由小于M的正整数组成。（显然还可以对其进行扩充。）如果是这种情况，那么算法很简单：使用一个大小为M称为Count的数组，它被初始化为全0。于是Count有M个单元（或称为桶），这些桶初始化为空。当读入A_i 时，Count[A_i]增1。在所有的输入数据读入后，扫描数组Count,打印出排序后的表。该算法用时O(M + N)。如果M = O(N)，那么总量就是O(N)。

尽管桶式排序看似太平凡用处不大，但是实际行却存在许多其输入只是一些小的整数的情况，使用像快速排序这样的排序方法真的是小题大作了。

迄今为止，我们考查过的所有算法都需要将输入数据装入内存。然而，存在一些应用程序，它们的输入数据量太大装不进内存。本节将讨论一些外部排序算法（external sort），它们是设计用来处理很大的输入的。

对于最一般的内部排序应用程序选用的方法不是插入排序、希尔排序，就是快速排序，它们的选用主要是根据输入的大小来决定。

高度优化的快速排序算法即使对于很少的输入数据也能和希尔排序一样快。快速排序的改进算法仍然有O(N²)的最坏情况，但是，这种最坏情形出现的机会是如此地微不足道，以至于不能成为影响算法的因素。如果需要对一些大型的文件排序，那么快速排序则是应该选用的方法。但是，永远都不要图省事而轻易把第一个元素用作枢纽元。对输入数据随机的假设是不安全的。如果你不想过多地考虑这个问题，那么你就使用希尔排序。希尔排序有些小缺陷，不过还是可以接受的，特别是需要简单明了的时候。希尔排序的最坏情况有只不过是O(N^4/3);这种最坏情况发生的几率也是微不足道的。

堆排序要比希尔排序慢，尽管它是一个带有明显紧凑内循环的O(NlogN)算法。

插入排序只用在小的或是非常接近排好序的输入数据上。我们没有包括进来归并排序，因为它的性能对于主存排序不如快速排序那么好，而且它的编程也一点也不省事。同时我们也看到，合并是外部排序的中心思想。