第九章 排序 概述 插入排序 快速排序 交换排序（起泡排序） 选择排序 归并排序

概述 排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据元素的有限集合。 排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。

排序算法的稳定性: 如果在元素序列中有两 个元素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面。如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

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

待排序数据表的类定义 #include <iostream.h> const int DefaultSize = 100; template <class T> class Element { //数据表元素定义 public: T key; //排序码 field otherdata; //其他数据成员 Element<T>& operator = (Element<T>& x) { key = x.key; otherdata = x.otherdata; return this; }

bool operator == (Element<T>& x) { return key == x. key; } //判 bool operator == (Element<T>& x) { return key == x.key; } //判*this与x相等 bool operator <= (Element<T>& x) { return key <= x.key; } //判*this小于或等于x bool operator >= (Element<T>& x) { return key >= x.key; } //判*this大于或等于x bool operator > (Element<T>& x) { return key > x.key; } //判*this大于x bool operator < (Element<T>& x) { return key < x.key; } //判*this小于x };

template <class T> class dataList { //数据表类定义 private: Element <T>* Vector; //存储排序元素的向量 int maxSize; //向量中最大元素个数 int currentSize; //当前元素个数 public: datalist (int maxSz = DefaultSize) : //构造函数 maxSize(maxSz), currentSize(0) { Vector = new Element<T>[maxSize]; } int Length() { return currentSize; } //取表长度

void Swap (Element<T>& x, Element<T>& y) { Element<T> temp = x; x = y; y = temp; } Element<T>& operator [](int i) //取第i个元素 { return Vector[i]; } int Partition (const int low, const int high); //快速排序划分 };

插入排序 (Insert Sorting) 基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。 直接插入排序 折半插入排序 希尔排序

直接插入排序 (Insert Sort) 基本思想是 : 当插入第i (i≥1) 个元素时，前面的V[0], V[1], …, V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

各趟排序结果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 2

21 25 49 25* 16 08 i = 3 0 1 2 3 4 5 0 1 2 3 4 5 temp 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 4 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 5

21 25 49 25* 16 08 0 1 2 3 4 5 完成 i = 4 时的排序过程 16 0 1 2 3 4 5 temp 21 25 49 25* 08 49 16 0 1 2 3 4 5 temp 21 25 25* 08 i = 4 j = 3 i = 4 j = 2

i = 4 j = 1 25* 16 21 25 49 08 0 1 2 3 4 5 i = 4 j = 0 49 16 25 25 25* 21 16 08 0 1 2 3 4 5 temp 0 1 2 3 4 5 temp 21 25 49 25* 08 16 i = 4 j = -1

直接插入排序的算法 #include "dataList.h" template <class T> void InsertSort (dataList<T>& L, int left, int right) { //依次将元素L.Vector[i]按其排序码插入到有序表 //L.Vector[left],…,L.Vector[i-1]中,使得 //L.Vector[left]到L.Vector[i]有序。 Element<T> temp; int i, j; for (i = left+1; i <= right; i++) if (L[i] < L[i-1]) { temp = L[i]; j = i-1;

do { L[j+1] = L[j]; j--; } while (j >= left && temp < L[j]); L[j+1] = temp; } };

设待排序元素个数为currentSize = n, 则该算法的主程序执行n-1趟。排序码比较次数和元素移动次数与元素排序码的初始排列有关。 最坏情况下, 第 i 趟时第 i 个元素必须与前面 i 个元素都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为 平均情况下，排序的时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。

折半插入排序 (Binary Insert Sort) 基本思想是 : 设在顺序表中有一 个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的元素。在插入V[i] 时, 利用折半搜索法寻找V[i] 的插入位置。

折半插入排序的算法 #include "dataList.h" template <class T> void BinaryInsertSort (dataList<T>& L, const int left, const int right) { //利用折半搜索, 在L.Vector[left]到L.Vector[i-1]中 //查找L.Vector[i]应插入的位置, 再进行插入。 Element<T> temp; int i, low, high, middle, k; for (i = left+1; i <= right; i++) { temp = L[i]; low = left; high = i-1; while (low <= high) { //折半搜索寻找插入位置 middle = (low+high)/2; //取中点

if (temp < L[middle]) //插入值小于中点值 high = middle-1; //向左缩小区间 else low = middle+1; //否则, 向右缩小区间 } for (k = i-1; k >= low; k--) L[k+1] = L[k]; //成块移动,空出插入位置 L[low] = temp; //插入 };

就平均性能来说，折半搜索比顺序搜索快, 所以折半插入排序比直接插入排序平均性能要快。 它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第 i 个元素时，需要经过 log2i +1 次排序码比较, 才能确定它应插入的位置。因此，将 n 个元素(为推导方便, 设为 n=2k ) 用折半插入排序所进行的排序码比较次数为： 折半插入排序是一种稳定的排序方法。

当 n 较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。 在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。 折半插入排序的元素移动次数与直接插入排序都依赖于元素的初始排列。

希尔排序 (Shell Sort) 希尔排序方法又称为缩小增量排序。该方法的基本思想是 : 设待排序元素序列有 n 个元素, 首先取一个整数 gap < n 作为间隔，将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1，将所有元素放在同一个序列中排序为止。

开始时 gap 的值较大，子序列中的元素较少，排序速度较快; 随着排序进展，gap 值逐渐变小, 子序列中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然很快。

21 25 49 25* 16 08 0 1 2 3 4 5 i = 1 Gap = 3

49 25* 25 21 16 08 0 1 2 3 4 5 i = 2 49 Gap = 2 25* 25 21 16 08 49 25* 25 21 16 08 49 25* 25 21 16 08

49 25* 25 21 16 08 0 1 2 3 4 5 i = 3 49 Gap = 1 25* 25 21 16 08

希尔排序的算法 #include "dataList.h" template <class T> void ShellSort (dataList<T>& L, const int left, const int right) { int i, j, gap = right-left+1; //增量的初始值 Element<T> temp; do { gap = gap/3+1; //求下一增量值 for (i = left+gap; i <= right; i++) if (L[i] < L[i-gap]) { //逆序 temp = L[i]; j = i-gap; L[j+gap] = L[j]; j = j-gap; } while (j >= left && temp < L[j]);

L[j+gap] = temp; //将vector[i]回送 } } while (gap > 1); };

gap的取法有多种。最初 Shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。Knuth 提出取 gap = gap/3 +1。还有人提出都取奇数为好，也有人提出各 gap 互质为好。 对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。 想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和元素平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。 希尔排序是一种不稳定的排序方法。

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

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

算法描述 QuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子序列 LeftList 和 RightList; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; }

i = 1 i = 2 i = 3 pivot 49 25 25* 21 16 08 0 1 2 3 4 5 pivot pivot 49 0 1 2 3 4 5 pivot pivot 49 i = 1 25* 25 21 16 08 pivot 49 i = 2 25* 25 21 16 08 49 i = 3 25* 25 21 16 08

i = 1 划分 pivotpos 49 25 25* 21 16 08 0 1 2 3 4 5 i 比较4次 交换25,16 pivotpos 49 25* 25 21 16 08 i 比较1次 交换49,08 pivotpos 49 25* 25 21 16 08 low pivotpos 49 25* 25 交换21,08 21 16 08

快速排序的算法 #include "dataList.h" template <class T> void QuickSort (dataList<T>& L, const int left, const int right) { //对元素Vector[left], ..., Vector[right]进行排序, //pivot=L.Vector[left]是基准元素, 排序结束后它的 //位置在pivotPos, 把参加排序的序列分成两部分, //左边元素的排序码都小于或等于它, 右边都大于它 if (left < right) { //元素序列长度大于1时 int pivotpos = L.Partition (left, right); //划分 QuickSort (L, left, pivotpos-1); QuickSort (L, pivotpos+1, right); } };

template <class T> int dataList<T>::Partition (const int low, const int high) { //数据表类的共有函数 int pivotpos = low; Element<T> pivot = Vector[low]; //基准元素 for (int i = low+1; i <= high; i++) //检测整个序列, 进行划分 if (Vector[i] < pivot) { pivotpos++; if (pivotpos != i) Swap(Vector[pivotpos],Vector[i]); } Vector[low] = Vector[pivotpos]; Vector[pivotpos] = pivot; //将基准元素就位 return pivotpos; //返回基准元素位置 };

算法quicksort是一个递归的算法, 其递归树如图所示。 从快速排序算法的递归树可知，快速排序的趟数取决于递归树的高度。 21 25* 25 49 08 16

最大递归调用层次数与递归树高度一致，理想情况为log2(n+1)。存储开销为 O(log2n)。 平均计算时间为 O(nlog2n)。 在最坏的情况，即待排序元素序列已经按其排序码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个元素的子序列。必须经过n-1 趟才能把所有元素定位，而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个元素的安放位置，总的排序码比较次数将达到

用第一个元素作为基准元素 快速排序退化的例子 初始 08 16 21 25 25* 49 08 i = 1 08 0 1 2 3 4 5 pivot 初始 08 16 21 25 25* 49 08 i = 1 08 16 21 25 25* 49 16 i = 2 08 16 21 25 25* 49 21 i = 3 08 16 21 25 25* 49 25 i = 4 08 16 21 25 25* 49 25* i = 5 08 16 21 25 25* 49 用第一个元素作为基准元素 快速排序退化的例子

其排序速度退化到简单排序的水平, 比直接插入排序还慢。占用附加存储(栈)将达到O(n)。 快速排序是一种不稳定的排序方法。 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。 因此，当n很小时可以用直接插入排序方法。

起泡排序 (Bubble Sort) 交换排序 ( Exchange Sort ) 基本思想是两两比较待排序元素的排序码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之。直到所有元素都排好序为止。 基本方法是：设待排序元素序列中的元素个数为 n。最多作 n-1 趟，i = 1, 2, , n-1。在第 i 趟中从后向前，j = n-1, n-2, , i，顺次两两比较V[j-1].key和V[j].key。如果发生逆序，则交换V[j-1]和V[j]。 又叫冒泡排序. 起泡排序 (Bubble Sort)

49 25 25* 21 16 08 0 1 2 3 4 5 49 i = 1 25 25* 21 16 08 Exchang=1 49 i = 2 25 25* 21 16 08 Exchang=1 49 i = 3 25 25* 21 16 08 Exchang=1

49 i = 4 25 25* 21 16 08 Exchang=0 0 1 2 3 4 5 起泡排序的算法 template <class T> void BubbleSort (dataList<T>& L, const int left, const int right) { int pass = left+1, exchange = 1; while (pass <= right && exchange) { exchange = 0; //标志为0假定未交换 for (int j = right; j >= pass; j--)

if (L[j-1] > L[j]) { //逆序 Swap (L[j-1], L[j]); //交换 exchange = 1; //标志置为1,有交换 } pass++; }; 算法分析 第i趟(1≤ in)对待排序元素序列V[i-1],V[i],,V[right]进行排序，结果将该序列中排序码最小的元素交换到序列的第一个位置(i-1)。

最多做n-1趟起泡就能把所有元素排好序。 在元素的初始排列已经按排序码从小到大排好序时，此算法只执行一趟起泡，做n-1次排序码比较，不移动元素。这是最好的情形。 最坏的情形是算法执行n-1趟起泡,第i趟 (1≤ in) 做n-i次排序码比较, 执行n-i次元素交换。在最坏情形下总的排序码比较次数KCN和元素移动次数RMN为： 起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。

选择排序 基本思想是: 每一趟 (例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序元素中选出排序码最小的元素，作为有序元素序列的第 i 个元素。待到第 n-2 趟作完，待排序元素只剩下1个, 就不用再选了。 直接选择排序 锦标赛排序 堆排序

直接选择排序 (Select Sort) 直接选择排序的基本步骤是： 在一组元素 V[i]～V[n-1] 中选择具有最小排序码的元素； 若它不是这组元素中的第一个元素, 则将它与这组元素中的第一个元素对调; 在这组元素中剔除这个具有最小排序码的元素。在剩下的元素V[i+1] ～ V[n-1]中重复执行第①、②步, 直到剩余元素只有一个为止。

i = 0 i = 1 i = 2 初始 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 49 25* 21 16 08 0 1 2 3 4 5 49 最小者 08 交换21,08 i = 0 25 25* 21 16 08 49 最小者 16 交换25,16 i = 1 25 25* 21 16 08 49 最小者 21 交换49,21 25* 25 i = 2 21 16 08

i = 3 i = 4 最小者 25* 无交换 最小者 25 无交换 结果 各趟排序后的结果 49 25* 25 21 16 08 0 1 2 3 4 5 49 最小者 25 无交换 i = 4 25* 25 21 16 08 49 结果 25* 25 21 16 08 各趟排序后的结果

直接选择排序的算法 #include "dataList.h" template <class T> void SelectSort (dataList<T>& L, const int left, const int right) { for (int i = left; i < right; i++) { int k = i; //在L[i]到L[right]之间找最小排序码元素 for (int j = i+1; j <= right; j++) if (L[j] < L[k]) k = j; if (k != i) Swap (L[i], L[k]); //交换 } };

i =1时选择排序的过程 0 1 2 3 4 5 16 08 25* 49 21 25 i k j 49  25 49 25 08 25* 16 21 i k j 25*  25

k 指示当前序列中最小者 49 08 25* 21 16 25 i k j 16 < 25 49 25 08 25* 16 21 0 1 2 3 4 5 i k j 21  16 k 指示当前序列中最小者

直接选择排序的排序码比较次数 KCN 与元素的初始排列无关。设整个待排序元素序列有 n 个元素，则第 i 趟选择具有最小排序码元素所需的比较次数总是 n-i-1 次。总的排序码比较次数为 元素移动次数与元素序列初始排列有关。 当这组元素初始状态是按其排序码从小到大有序的时候, 元素的移动次数达到最少RMN = 0， 最坏情况是每一趟都要进行交换，总的元素移动次数为 RMN = 3(n-1)。 直接选择排序是一种不稳定的排序方法。

锦标赛排序 (Tournament Sort) 它的思想与体育比赛时的淘汰赛类似。首先取得 n 个元素的排序码，进行两两比较，得到 n/2 个比较的优胜者(排序码小者)，作为第一步比较的结果保留下来。然后对这 n/2 个元素再进行排序码的两两比较, …, 如此重复，直到选出一个排序码最小的元素为止。 由于每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，所以称这种比赛树为胜者树。

在图例中，最下面是元素排列的初始状态，相当于一棵完全二叉树的叶结点，它存放的是所有参加排序的元素的排序码。 08 Winner 21 25* 25 49 16 63 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6]

e[6] = 08 排序码比较次数 : 6 Winner (胜者) 08 21 25 49 16 63 25* e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. VS. VS. VS. 形成初始胜者树（最小排序码上升到根） 排序码比较次数 : 6

e[5] = 16 输出冠军e[6] = 08 并调整胜者树后树的状态 排序码比较次数 : 3 ∞ Winner (胜者) 16 21 25 25* 25 49 ∞ 63 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[6] = 08 并调整胜者树后树的状态 排序码比较次数 : 3

e[1] = 21 输出冠军e[5] = 16 并调整胜者树后树的状态 排序码比较次数 : 3 ∞ Winner (胜者) 21 63 25 25* 25 49 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[5] = 16 并调整胜者树后树的状态 排序码比较次数 : 3

e[2] = 25 输出冠军e[1] = 21 并调整胜者树后树的状态 排序码比较次数 : 3 ∞ Winner (胜者) 25 63 49 25* 49 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[1] = 21 并调整胜者树后树的状态 排序码比较次数 : 3

e[4] = 25* 输出冠军e[2] = 25 并调整胜者树后树的状态 排序码比较次数 : 3 ∞ Winner (胜者) 63 49 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[2] = 25 并调整胜者树后树的状态 排序码比较次数 : 3

输出冠军e[4] = 25* 并调整胜者树后树的状态 排序码比较次数 : 3 Winner (胜者) e[3] = 49 49 63 ∞ e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[4] = 25* 并调整胜者树后树的状态 排序码比较次数 : 3

e[7] = 63 输出冠军e[3] = 49 并调整胜者树后树的状态 排序码比较次数 : 3 ∞ Winner (胜者) 63 e[1] e[2] e[3] e[4] e[5] e[6] e[7] t[1] t[2] t[3] t[4] t[5] t[6] VS. VS. VS. 输出冠军e[3] = 49 并调整胜者树后树的状态 排序码比较次数 : 3

胜者树是完全二叉树, 其高度为 log2n , 其中 n 为待排序元素个数。 除第一次选择具有最小排序码的元素需要进行 n-1 次排序码比较外, 重构胜者树选择次小、再次小排序码所需的比较次数均为 O(log2n)。总排序码比较次数为O(nlog2n)。

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

堆排序 (Heap Sort) 利用堆及其运算, 可以很容易地实现选择排序的思路。 堆排序分为两个步骤 根据初始输入数据，利用堆的调整算法 siftDown( ) 形成初始堆; 通过一系列的元素交换和重新调整堆进行排序。 为了实现元素按排序码从小到大排序，要求建立最大堆。

建立初始的最大堆 21 25 25* 49 16 08 1 2 3 4 5 i 21 25 49 25* 16 08 初始排序码集合 i = 2 时的局部调整

i 21 49 1 1 2 2 25 49 25 21 3 4 5 3 4 5 25* 16 08 25* 16 08 21 25 49 25* 16 08 49 25 21 25* 16 08 i = 1 时的局部调整 i = 0 时的局部调整 形成最大堆

最大堆的向下调整算法 template <class T> siftDown (dataList<T>& L, const int start, const int m){ //私有函数: 从结点start开始到m自上向下比较, //如果子女的值大于双亲的值, 则相互交换, 将一 //个集合局部调整为最大堆。 int i = start; int j = 2*i+1; //j是i的左子女 Element<T> temp = L[i]; //暂存子树根结点 while (j <= m) { //逐层比较 if (j < m && L[j] < L[j+1]) j++; //让j指向两子女中的大者 if (temp >= L[j]) break; //temp排序码大,不调整

else { //否则子女中的大者上移 L[i] = L[j]; i = j; j = 2 else { //否则子女中的大者上移 L[i] = L[j]; i = j; j = 2*j+1; //i下降到子女位置 } L[i] = temp; //temp放到合适位置 };

基于初始堆进行堆排序 最大堆堆顶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个元素重新调整，…。 如此反复执行，最后得到全部排序好的元素序列。这个算法即堆排序算法，其细节在下面的程序中给出。

49 08 1 1 2 2 25 21 25 21 3 4 5 3 4 5 25* 16 08 25* 16 49 49 25 21 25* 16 08 08 25 21 25* 16 49 初始最大堆 交换 0 号与 5 号元素, 5 号元素就位

25 16 1 1 2 2 25* 21 25* 21 3 4 5 3 4 5 08 16 49 08 25 49 25 25* 21 08 16 49 16 25* 21 08 25 49 从 0 号到 4 号 重新 调整为最大堆 交换 0 号与 4 号元素, 4 号元素就位

25* 08 1 1 2 2 16 21 16 21 3 4 5 3 4 5 08 25 49 25* 25 49 25* 16 21 08 25 49 08 16 21 25* 25 49 从 0 号到 3 号 重新 调整为最大堆 交换 0 号与 3 号元素, 3 号元素就位

21 08 1 1 2 2 16 08 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 21 16 08 25* 25 49 08 16 21 25* 25 49 从 0 号到 2 号 重新 调整为最大堆 交换 0 号与 2 号元素, 2 号元素就位

16 08 1 1 2 2 08 21 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 16 08 21 25* 25 49 08 16 21 25* 25 49 从 0 号到 1 号 重新 调整为最大堆 交换 0 号与 1 号元素, 1 号元素就位

堆排序的算法 template <class T> void HeapSort (dataList<T>& L) { //对表L.Vector[0]到L.Vector[n-1]进行排序, 使得表 //中各个元素按其排序码非递减有序 int i, n = L.length(); for (i = (n-2)/2; i >= 0; i--) //将表转换为堆 siftDown (L, i, n-1); for (i = n-1; i >= 0; i--) { //对表排序 L.Swap(0, i); siftDown (L, 0, i-1); } };

第二个 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 所指位置中； 08 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 right L1 i j 08 16 21 25 25* 37 49 54 62 72 93 left right k L2 当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的元素排放到新表 k 所指位置中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。

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

迭代的归并排序算法 21 25 49 25* 93 62 72 08 37 16 54 len=1 len=2 21 25 25* 49 62 93 08 72 16 37 54 len=4 21 25 25* 49 08 62 72 93 16 37 54 len=8 08 21 25 25* 49 62 72 93 16 37 54 len=16 08 16 21 25 25* 37 49 54 62 72 93

两路归并算法 #include "dataList.h" template <class T> void merge (dataList<T>& L1, dataList<T>& L2, const int left, const int mid, const int right) { //L1.Vector[left..mid]与L1.Vector[mid+1..right]是两 //个有序表, 将这两个有序表归并成一个有序表 //L2.Vector[left..right] int k, i, j; i = left; j = mid+1; k = left; //i, j是检测指针, k是存放指针

while (i <= mid && j <= right) //两两比较 if (L1[i] <= L1[j]) L2[k++] = L1[i++]; else L2[k++] = L1[j++]; while (i <= mid) L2[k++] = L1[i++]; //若第一个表未检测完,复制 while (j <= right) L2[k++] = L1[j++]; //若第二个表未检测完,复制 };

一趟归并排序的算法 设L1.Vector[0..n-1]中 n 个记录已经分为一些长度为 len 的归并项，将这些归并项两两归并成长度为2len的归并项, 结果放到L2[ ]中。 如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情形： 剩下一个长度为len的归并项和另一个长度不足len的归并项, 可用merge算法将它们归并成一个长度小于 2len 的归并项。 只剩下一个归并项，其长度小于或等于 len, 将它直接复制到结果表中。

template <class T> void MergePass (dataList<T>& L1, datalist<T>& L2, const int len) { int i = 0, j, n = L1.Length(); while (i+2*len <= n-1) { merge (L1, L2, i, i+len-1, i+2*len-1); i += 2 * len; //循环两两归并 } if (i+len <= n-1) merge (L1, L2, i, i+len-1, n-1); else for (j = i; j <= n-1; j++) L2[j] = L1[j]; };

(两路)归并排序的主算法 template <class T> void MergeSort (dataList<T>& L) { //按元素排序码非递减的顺序对表L中元素排序 int n = L.Length(); dataList<T> & tempList (n); //创建临时表 int len = 1; while (len < n) { MergePass (L, tempList, len); len *= 2; MergePass (tempList, L, len); len *= 2; } };

在迭代的归并排序算法中, 函数MergePass()做一趟两路归并排序, 要调用merge()函数 n/(2 在迭代的归并排序算法中, 函数MergePass()做一趟两路归并排序, 要调用merge()函数 n/(2*len)  O(n/len) 次, 函数MergeSort()调用MergePass()正好log2n次，而每次merge()要执行比较O(len)次, 所以算法总的时间复杂度为O(nlog2n)。 归并排序占用附加存储较多, 需要另外一个与原待排序元素数组同样大小的辅助数组。这是这个算法的缺点。 归并排序是一个稳定的排序方法。

各种排序方法的比较 排 序 方 法 比较次数 移动次数 稳定 性 附加存储 最好 最差 直接插入排序 O(n) O(n2)  O(1)  O(1) 折半插入排序 O(n log2n) 起泡排序 快速排序  O(log2n) 直接选择排序 锦标赛排序 堆排序 归并排序