排序

概述

• 排序：将一组杂乱无章的数据按一定的规律顺次排列起来。

• 数据表(datalist): 它是待排序数据元素的有限集合。

• 排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。

• 排序算法的稳定性: 如果在元素序列中有两 个元素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面。如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。

• 内排序与外排序: 内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

• 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
• 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的算法，需要按最好情况和最坏情况进行估算。

• 算法执行时所需的附加存储: 评价算法好坏的另一标准。

插入排序 (Insert Sorting)

直接插入排序

折半插入排序

• 就平均性能来说，折半搜索比顺序搜索快, 所以折半插入排序比直接插入排序平均性能要快。

• 它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第 i 个元素时，需要经过 log2i +1 次排序码比较, 才能确定它应插入的位置。因此，将 n 个元素(为推导方便, 设为 n=2k ) 用折半插入排序所进行的排序码比较次数为：

• 折半插入排序是一种稳定的排序方法。

• 当 n 较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。

• 在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。

• 折半插入排序的元素移动次数与直接插入排序都依赖于元素的初始排列。

希尔排序

• gap的取法有多种。最初 Shell 提出取 ，，直到gap = 1。Knuth 提出取 。还有人提出都取奇数为好，也有人提出各 gap 互质为好。

• 对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

• Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和元素平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

• 希尔排序是一种不稳定的排序方法。

交换排序

冒泡排序

• 第i趟对待排序元素序列进行排序，结果将该序列中排序码最小的元素交换到序列的第一个位置(i-1)。

• 最多做n-1趟起泡就能把所有元素排好序。

• 在元素的初始排列已经按排序码从小到大排好序时，此算法只执行一趟起泡，做n-1次排序码比较，不移动元素。这是最好的情形。

• 最坏的情形是算法执行n-1趟起泡,第i趟 (1≤ in) 做n-i次排序码比较, 执行n-i次元素交换。在最坏情形下总的排序码比较次数KCN和元素移动次数RMN为：

• 起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。

快速排序 (Quick Sort)

• 基本思想是任取待排序元素序列中的某个元素 (例如取第一个元素) 作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：
• 左侧子序列中所有元素的排序码都小于或等于基准元素的排序码
• 右侧子序列中所有元素的排序码都大于基准元素的排序码

• 基准元素则排在这两个子序列中间(这也是该元素最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的元素都排在相应位置上为止。

• 伪代码描述

• Code

• 算法quicksort是一个递归的算法, 其递归树如图所示。

• 从快速排序算法的递归树可知，快速排序的趟数取决于递归树的高度。

• 最大递归调用层次数与递归树高度一致，理想情况为log2(n+1)。存储开销为 O(log2n)。平均计算时间为 O(nlog2n)。

• 在最坏的情况，即待排序元素序列已经按其排序码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个元素的子序列。必须经过n-1 趟才能把所有元素定位，而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个元素的安放位置，总的排序码比较次数将达到

• 其排序速度退化到简单排序的水平, 比直接插入排序还慢。占用附加存储(栈)将达到O(n)。

• 快速排序是一种不稳定的排序方法。

• 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。

• 因此，当n很小时可以用直接插入排序方法。

选择排序

直接选择排序

• 在一组元素 V[i]～V[n-1] 中选择具有最小排序码的元素；

• 若它不是这组元素中的第一个元素, 则将它与这组元素中的第一个元素对调;

• 在这组元素中剔除这个具有最小排序码的元素。在剩下的元素V[i+1] ～ V[n-1]中重复执行第①、②步, 直到剩余元素只有一个为止。

锦标赛排序 (Tournament Sort)

• 它的思想与体育比赛时的淘汰赛类似。首先取得 n 个元素的排序码，进行两两比较，得到 n/2 个比较的优胜者(排序码小者)，作为第一步比较的结果保留下来。然后对这 n/2 个元素再进行排序码的两两比较, …, 如此重复，直到选出一个排序码最小的元素为止。

• 由于每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，所以称这种比赛树为胜者树。

• 在图例中，最下面是元素排列的初始状态，相当于一棵完全二叉树的叶结点，它存放的是所有参加排序的元素的排序码。

• 胜者树是完全二叉树, 其高度为  , 其中 n 为待排序元素个数。

• 除第一次选择具有最小排序码的元素需要进行 n-1 次排序码比较外, 重构胜者树选择次小、再次小排序码所需的比较次数均为 O(log2n)。总排序码比较次数为O(nlog2n)。

• 这种排序方法虽然减少了许多排序时间, 但是使用了较多的附加存储。如果有 n 个元素，必须使用至少 2n-1 个结点来存放胜者树。

• 锦标赛排序是一个稳定的排序方法。

堆排序

• 利用堆及其运算, 可以很容易地实现选择排序的思路。

• 堆排序分为两个步骤根据初始输入数据，利用堆的调整算法 siftDown( ) 形成初始堆；通过一系列的元素交换和重新调整堆进行排序。

• 为了实现元素按排序码从小到大排序，要求建立最大堆。

• 最大堆堆顶L.Vector[0]具有最大的排序码，将L.Vector[0]与L.Vector[n-1]对调, 把具有最大排序码的元素交换到最后，再对前面的n-1个元素, 使用堆的调整算法siftDown(L, 0, n-2)，重新建立最大堆，具有次最大排序码的元素又上浮到L.Vector[0]位置。

• 再对调L.Vector[0]和L.Vector[n-2]，再调用siftDown(L, 0, n-3), 对前面的n-2个元素重新调整，…。

• 如此反复执行，最后得到全部排序好的元素序列。这个算法即堆排序算法，其细节在下面的程序中给出。

• 第二个 for 循环中调用了n-1次siftDown()算法, 该循环的计算时间为O(nlog2n)。因此, 堆排序的时间复杂性为O(nlog2n)。

• 该算法的附加存储主要是在第二个 for 循环中用来执行元素交换时所用的一个临时元素。因此，该算法的空间复杂性为O(1)。

• 堆排序是一个不稳定的排序方法。

归并排序 (Merge Sort)

• 归并，是将两个或两个以上的有序表合并成一个新的有序表。

• 元素序列L1中有两个有序表Vector[left, ..., mid]和Vector[mid+1, ... , right]。它们可归并成一个有序表, 存于另一元素序列L2的Vector[left, ..., right] 中。

• 这种方法称为两路归并 (2-way merging)。变量 i 和 j 分别是表Vector[left, ..., mid]和Vector[mid+1, ... , right]的检测指针。k 是存放指针。
• 当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的元素排放到新表 k 所指位置中；
• 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。

迭代的归并排序算法

• 迭代的归并排序算法就是利用两路归并过程进行排序。

• 其基本思想是： 设初始元素序列有 n 个元素，首先把它看成是 n 个长度为 1 的有序子序列（归并项），做两两归并，得到 n/2 个长度为 2 的归并项（最后一个归并项的长度可能为1）；再做两两归并，得到 n/4 个长度为 4 的归并项（最后一个归并项长度可以短些）…，如此重复，最后得到一个长度为 n 的有序序列。

• 代码

一趟归并排序的算法

• 设L1.Vector[0..n-1]中 n 个记录已经分为一些长度为 len 的归并项，将这些归并项两两归并成长度为2len的归并项, 结果放到L2[ ]中。

• 如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情形：
• 剩下一个长度为len的归并项和另一个长度不足len的归并项, 可用merge算法将它们归并成一个长度小于 2len 的归并项。
• 只剩下一个归并项，其长度小于或等于 len, 将它直接复制到结果表中。

• 主算法

• 在迭代的归并排序算法中, 函数MergePass()做一趟两路归并排序, 要调用merge()函数 次, 函数MergeSort()调用MergePass()正好log2n次，而每次merge()要执行比较O(len)次, 所以算法总的时间复杂度为O(nlog2n)。

• 归并排序占用附加存储较多, 需要另外一个与原待排序元素数组同样大小的辅助数组。这是这个算法的缺点。

• 归并排序是一个稳定的排序方法。