第10章 排序

本章主要内容 排序的基本概念 交换排序 冒泡排序 快速排序 插入排序 希尔排序 堆排序 归并排序 基数排序

排序的基本概念 排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序的基本概念 排序的分类 1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中 2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

排序的基本概念 排序算法的性能指标 1. 时间开销： 2. 空间开销： 3. 算法的稳定性 ⑴比较：关键码之间的比较； ⑵移动：记录从一个位置移动到另一个位置。 2. 空间开销： 辅助存储空间 3. 算法的稳定性

排序算法的存储结构 从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。 假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。 int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用 假定2：将待排序的记录序列排序为升序序列。

10.2 交换排序（冒泡排序） 交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。

冒泡排序需解决的关键问题 ⑴ 在一趟冒泡排序中，若有多个记录位于最终位置，应如何记录？ ⑵ 如何确定冒泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？ ⑶ 如何判别冒泡排序的结束？

问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记录是否发生交换。

问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 12 交换 38 交换 53 交换 05 98 12 69 38 53 81 05 98 69 81

问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 算法描述： if （r[j]>r[j+1]）{ r[j]←→r[j+1]； exchange=j； }

问题2：如何确定冒泡排序的范围？ 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟冒泡排序的范围是r[1] ~ r[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 算法描述： bound=exchange; for (j=1; j<bound; j++) if （r[j]>r[j+1]） { r[j]<->r[j+1]； exchange=j； }

问题3：如何判别冒泡排序的结束？ 解决方法： 在每一趟冒泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录交换，exchange的值就会大于0。 这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录交换，从而判别整个冒泡排序的结束。 算法描述： while (exchange) { 执行一趟冒泡排序； }

void BubbleSort(int r[ ], int n) { exchange=n; while (exchange) bound=exchange; exchange=0； for (j=1; j<bound; j++) if (r[j]>r[j+1]) r[j]←→r[j+1]； exchange=j； }

冒泡排序的时间性能分析 最好情况（正序）： 比较次数：n-1 移动次数：0 时间复杂度为O(n)。

冒泡排序的时间性能分析 最坏情况（反序）： 比较次数： å 移动次数： 时间复杂度为O(n2)。 平均情况：时间复杂度为O(n2)。 5 4 3 2 1 最坏情况（反序）： 4 3 2 1 5 比较次数： 移动次数： 2 ) 1 ( - = å n (n-i) n-1 i 3n 3(n-i) 3 2 1 4 5 2 1 3 4 5 1 2 3 4 5 时间复杂度为O(n2)。 平均情况：时间复杂度为O(n2)。

冒泡排序的性能分析 在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。 冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。 冒泡排序是一种稳定的排序方法。

如何进一步优化冒泡排序? 需扫描1趟 需扫描n-1趟 需扫描2趟 需扫描n-2趟 造成不对称的原因是什么? 1 2 3 4 5 5 4 3

如何改变不对称性? 在排序过程中交替改变扫描方向——双向冒泡排序 2 3 4 5 1 2 3 4 1 5 1 2 3 4 5

冒泡排序的改进思考 改进的着眼点：在冒泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较次数和移动次数较多。 减少总的比较次数和移动次数 增大记录的比较和移动距离 较大记录从前面直接移动到后面 较小记录从后面直接移动到前面

10.2 交换排序（快速排序） 首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。 需解决的关键问题： ⑴如何选择轴值？ ⑵如何实现分割（称一次划分）？ ⑶如何处理分割得到的两个待排序子序列？ ⑷如何判别快速排序的结束？

问题1：如何选择轴值？ 选择轴值的方法： 选取不同轴值的效果： 1.使用第一个记录的关键码； 2.选取序列中间记录的关键码； 3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置； 4.随机选取轴值。 选取不同轴值的效果： 决定两个子序列的长度，子序列的长度最好相等。

问题2：如何实现一次划分？ 65 55 50 49 38 27 13 i j j j 65 27 50 49 55 13 38 i i i j 13 65 27 50 49 38 55 i j j j

问题2：如何实现一次划分？ 解决方法： ① 取第一个记录的关键字值作为基准，将第一个记录暂存于temp中，设两个变量i，j分别指示将要划分的最左、最右记录的位置。 ② 将j指向的记录关键字值与基准值进行比较，如果j指向的记录关键字值大，则j前移一个位置；重复此过程，直到j指向的记录关键字值小于基准值；若i<j，则将j指向的记录移到i所指位置。 ③ 将i指向的记录关键字值与基准值进行比较，如果i指向的记录关键字值小，则i后移一个位置；重复此过程，直到i指向的记录关键字值大于基准；若i<j，则i指向的记录移到j所指位置。 ④ 重复②、③步，直到i=j。

问题2：如何实现一次划分？

问题2：如何实现一次划分？ 算法描述： int Partition(Record r[ ], int i, int j) { temp= r[i]; while (i<j) { while (i<j && r[j].key>= temp.key) j--； if (i<j) r[i++]= r[j]; while (i<j && r[i].key<= temp.key) i++; if (i<j) r[j--]= r[i]; } r[i] = temp; return i;

问题3：如何处理分割得到的两个待排序子序列？ 解决方法： 对分割得到的两个子序列递归地执行快速排序。 13 27 50 38 49 55 65 i j i j 65 50 49 55 38 13 27

问题3：如何处理分割得到的两个待排序子序列？ 算法描述： void QuickSort (Record r[ ], int i, int j ) { if (i<j) { pivot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); } 初始调用为QuickSort(r, 1, n)

问题4：如何判别快速排序的结束？ 解决方法： 若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。 void QuickSort (Record r[ ], int i, int j ) { if (i<j) { pivot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); }

快速排序的时间性能分析 å ) ( 1 2 n O i = - ） （ 最好情况： 每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。 最坏情况： 每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。 ) ( 1 2 n O i = - å ） （ 平均情况：为O(nlog2n)。

快速排序的性能分析 快速排序是一种不稳定的排序方法。 请举例说明。

10.3 插入排序 插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。 两种插入排序方法：直接插入排序和折半插入排序。

10.3.1 直接插入排序 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。 r1 r2 ri-1 ri rn …… 有序序列 无序序列 r'1 r'2 r'i-1 r'i …… rn ri+1 ……

10.3.1 直接插入排序 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。 需解决的关键问题： （1）如何构造初始的有序序列？ （2）如何查找待插入记录的插入位置?

直接插入排序过程示例 i = 2 r[0]的作用? i = 3 暂存单元 i = 4 监视哨 i = 5 i = 6 21 25 22 10 25* 18 i = 2 18 22 10 25* 25 21 r[0]的作用? i = 3 18 22 10 25* 22 21 25 暂存单元 18 10 25* i = 4 10 25 22 21 监视哨 18 25* i = 5 25 25 21 15 10 18 i = 6 18 25* 25 21 15 10 15 10 18 25* 25 21

问题1：如何构造初始的有序序列 解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第 n个记录插入。 算法描述： for (i=2; i<=n; i++) { 插入第i个记录，即第i趟直接插入排序； }

问题2：如何查找待插入记录的插入位置? 算法描述： r[0]=r[i]; j=i-1; while (r[0]<r[j]) { 解决方法： 在i-1个记录的有序区r[1] ~ r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。 算法描述： r[0]=r[i]; j=i-1; while (r[0]<r[j]) { r[j+1]=r[j]; j--; } r[0]有两个作用： 1. 进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容； 2. 在查找插入位置的循环中充当哨兵。

直接插入排序的时间性能分析 最好情况下（正序）： 比较次数：n-1 移动次数：2(n-1) 时间复杂度为O(n)。 5 4 3 2 1 比较次数：n-1 移动次数：2(n-1) 4 5 3 2 1 时间复杂度为O(n)。 最坏情况下（逆序或反序）： 比较次数： 移动次数： 2 ) 1 )( ( - + = å n i 4 ） （ 时间复杂度为O(n2)。

直接插入排序的时间性能分析 平均情况下（随机排列）： 比较次数： 移动次数： å 时间复杂度为O(n2)。 4 ) 1 )( ( - + = i （ ） 时间复杂度为O(n2)。

直接插入排序的性能分析 空间性能：需要一个记录的辅助空间。 直接插入排序算法是一种稳定的排序算法。 直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。 当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。 如何改进直接插入排序？

10.3.2 折半插入排序 void BinInsertSort(Record r[ ], int n) { for (i=1; i<n; i++) { temp=r[i], low=0; high=i-1; while (low<=high) { mid=(low+high)/2 if (temp.key<r[mid].key) high=mid-1; else low=mid+1; } for (j=i-1; j>=low; j--) r[j+1]=r[j]; r[low]=temp;

10.3.2 折半插入排序 采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最多为折半查找判定树的深度 如插入第i个元素时，则需进行log2i次比较，因此插入n1个元素的平均比较次数为O(nlog2n)。 折半插入排序法与直接插入排序法相比较，虽然改善了算法中比较次数的数量级为O(nlog2n)，但其并未改变移动元素的时间耗费，所以折半插入排序总的时间复杂度仍然是O(n2)。

10.3.3 希尔排序 对直接插入排序进行改进 改进的着眼点： （1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高； 10.3.3 希尔排序 对直接插入排序进行改进 改进的着眼点： （1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高； （2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。

10.3.3 希尔排序 基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。 需解决的关键问题? （1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？ （2）子序列内如何进行直接插入排序？

10.3.3 希尔排序 分割待排序记录的目的? 启示? 1. 减少待排序记录个数； 10.3.3 希尔排序 分割待排序记录的目的? 1. 减少待排序记录个数； 2. 使整个序列向基本有序发展。 基本有序：例如{1, 2, 8, 4, 5, 6, 7, 3, 9}； 局部有序：例如{6, 7, 8, 9, 1, 2, 3, 4, 5}。 局部有序不能提高直接插入排序算法的时间性能。 启示? 子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。

希尔插入排序过程示例 d = 4 d = 2 d = 1 1 2 3 4 5 6 7 8 9 初始序列 40 25 49 25* 16 21 1 2 3 4 5 6 7 8 9 初始序列 40 25 49 25* 16 21 08 30 13 d = 4 40 21 25 49 25* 16 30 08 13 13 16 40 25 21 08 49 25* 30 d = 2 13 25 21 08 25* 16 30 49 40 08 13 16 40 49 25 21 25* 30 d = 1 08 25 21 13 25* 16 30 40 49 08 25 13 16 21 25* 40 30 49

问题1：应如何分割待排序记录？ 解决方法： 将相隔某个“增量”的记录组成一个子序列。 增量应如何取？ 希尔最早提出的方法是d1=n/2，di+1=di/2。 算法描述： for (d=n/2; d>=1; d=d/2) { 以d为增量，进行组内直接插入排序； }

问题2：子序列内如何进行直接插入排序？ 解决方法： 在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。当搜索位置＜0，表示插入位置已找到。 在搜索过程中，记录后移也是跳跃d个位置。 在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。

问题2：子序列内如何进行直接插入排序？ 算法描述： void ShellSort(Record r[ ], int n) { for (d=n/2;d>=1;d=d/2) //以增量d进行直接插入排序 for (i=d; i<n; i++) temp=r[i]; //暂存被插入记录 for (j=i-d; j>0 && temp.key<r[j].key; j=j-d) r[j+d]=r[j]; //记录后移 d个位置 r[j+d]=temp }

希尔排序算法的时间性能 希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。 希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。 研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。

10.4 选择排序 选择排序的主要操作是选择，其主要思想是:每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。

10.4.1 简单选择排序 简单选择排序的主要思想是： 需解决的关键问题? 10.4.1 简单选择排序 简单选择排序的主要思想是： 第i 趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。 需解决的关键问题? ⑴如何在待排序序列中选出关键码最小的记录？ ⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置？

简单选择排序示例 49 最小者 08 交换21,08 25 28 21 i = 1 16 08 08 28 49 16 25 最小者 16 交换25,16 08 21 i = 2 21 08 28 49 最小者 21 交换49,21 i = 3 16 25 21

简单选择排序示例 49 21 最小者 25 交换25,28 08 28 16 25 25 i = 4 49 21 08 16 最小者 28 不交换 28 25 28 i = 5 49 21 08 16 28 25 无序区只有 一个记录

问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 49 25 28 21 16 08 08 k k k

问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 算法描述： k=i; for (j=i+1; j<=n; j++) if (r[j]<r[k]) k=j;

问题2：如何确定最小记录的最终位置？ 解决方法： 第i趟简单选择排序的待排序区间是r[i] ~ r[n]，则r[i]是无序区第一个记录，所以，将index所记载的关键码最小的记录与r[i]交换。 算法描述： if (k!=i) r[i]←→r[k];

简单选择排序算法 void SelectSort (Record r[ ], int n) { for (i=0; i<n-1; i++) { k=i; for (j=i+1; j<n; j++) if (r[j].key<r[k].key) k=j; if (k!=i) {temp=r[i]; r[i]=r[k]; r[k]=temp; } }

简单选择排序算法的性能分析 å 移动次数： 最好情况（正序）：0次 最坏情况：3(n-1)次 比较次数： ) ( 1 2 n O i = - 4 5 2 3 1 1 5 2 3 4 1 2 最坏情况：3(n-1)次 5 3 4 1 2 3 比较次数： 5 4 1 2 3 4 ) ( 1 2 n O i = - å ） （ 5 1 2 3 4 简单选择排序的时间复杂度为O(n2)。 空间性能：需一个辅助空间。 稳定性：是一种稳定的排序算法。

10.4.2 堆排序 简单选择排序的改进 改进的着眼点： 如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。

堆的定义 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 18 20 32 36 45 25 38 50 40 28 1. 小根堆的根结点是所有结点的最小者。 2. 较小结点靠近根结点，但不绝对。

堆的定义 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 50 38 45 40 28 36 32 20 18 1. 大根堆的根结点是所有结点的最大者。 2. 较大结点靠近根结点，但不绝对。

堆和序列的关系 50 38 45 40 28 36 32 20 18 采用顺序存储 50 38 45 32 36 40 28 20 18 28 1 2 3 4 5 6 7 8 9 10 将堆用顺序存储结构来存储，则堆对应一组序列。

10.4.2 堆排序 基本思想：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。 需解决的关键问题? ⑴如何由一个无序序列建成一个堆（即初始建堆）？ ⑵如何处理堆顶记录？ ⑶如何调整剩余记录，成为一个新堆（即重建堆）？

堆调整 在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？ 28 36 32 16 18 25 36

堆调整——算法描述： void sift ( int r[ ], int k, int m ) {//要筛选结点的编号为k，堆中最后一个结点的编号为m i=k; j=2*i; //将筛选记录暂存 while (j<=m ) //筛选还没有进行到叶子 { if (j<m && r[j]<r[j+1]) j++; //左右孩子中取较大者 if (r[i]>r[j]) break; else { r[i] ←→r[j]; //将筛选记录移到正确位置 i=j; j=2*i; }

问题1：如何由一个无序序列建成一个堆？ 28 25 16 32 18 36 28 25 18 36 16 25 32 16 32 16 28 28 32 36 28 18 36 25 16 18 25

问题1：如何由一个无序序列建成一个堆？ 算法描述： for (i=n/2; i>=1; i--) sift(r, i, n) ; 最后一个结点（叶子）的序号是n， 则最后一个分支结点即为结点n的双亲， 其序号是n/2。

问题2：如何处理堆顶记录？ 32 36 28 16 18 25 32 16 28 36 18 25 对 应 对 应 36 28 32 25 18 16 1 2 3 4 5 6 16 28 32 25 18 36 1 2 3 4 5 6 交换

问题2：如何处理堆顶记录？ 解决方法： 第 i 次处理堆顶是将堆顶记录r[1]与序列中第n-i+1个记录r[n-i+1]交换。 算法描述： r[1]←→r[n-i+1];

问题3：如何调整剩余记录，成为一个新堆？ 32 16 28 36 18 25 16 28 16 28 32 36 18 32 36 18 25 16 25

问题3：如何调整剩余记录，成为一个新堆？ 解决方法： 第 i 次调整剩余记录，此时，剩余记录有n-i个，调整根结点至第n-i个记录。 算法描述： sift(r, 1, n-i);

堆排序算法 void HeapSort ( int r[], int n) { for (i=n/2; i>=1; i--) //初建堆 sift(r, i, n) ; for (i=1; i>n; i++ ) r[1]←→r[n-i+1]; //移走堆顶 sift(r, 1, n-i); //重建堆 }

堆排序算法的性能分析 第1个for循环是初始建堆，需要O(n)时间； 第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第 i 次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间； 因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。

10.5 归并排序 归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。 10.5 归并排序 归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。 归并：将两个或两个以上的有序序列合并成一个有序序列的过程。

10.5 归并排序 基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。 需解决的关键问题? ⑴如何将两个有序序列合成一个有序序列？ ⑵怎样完成一趟归并？ ⑶如何控制二路归并的结束？

问题1：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 i i j j j 5 20 31 60 k

问题1：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 i i j j j 归并可以就地进行吗? 5 20 31 60 k

问题1：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 i i j j j 在归并过程中，可能会破坏原来的有序序列，所以，将归并的结果存入另外一个数组中。 5 20 31 60 k

问题1：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 i i j j j 子序列的长度一定相等吗? 5 20 31 60 k

问题1：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 i i j j j 5 20 31 60 k

问题1：如何将两个有序序列合成一个有序序列？ 设相邻的有序序列为r[s] ~ r[m]和r[m+1] ~ r[t]，归并成一个有序序列r1[s] ~ r1[t] s m m+1 t r[ ] r1[ ] i j k

问题1：如何将两个有序序列合成一个有序序列？ 算法描述： void Merge (int r[ ], int r1[ ], int s, int m, int t ) { i=s; j=m+1; k=s; while (i<=m && j<=t) if (r[i]<=r[j]) r1[k++]=r[i++]; else r1[k++]=r[j++]; } if (i<=m) while (i<=m) //收尾处理 r1[k++]=r[i++]; //前一个子序列 else while (j<=t) r1[k++]=r[j++]; //后一个子序列

问题2：怎样完成一趟归并？ 60 20 31 5 44 55 65 60 20 31 5 44 55 65 20 60 5 31 44 55 65 5 20 31 60 44 55 65 在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度h表示。

设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： 问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ①若i≤n-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并； h i=1 n-2h+1=4 20 60 5 31 44 55 65 i n-2h+1

设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： 问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ①若i≤n-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并； 算法描述： while (i≤n-2h+1) { Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; }

设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： 问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ②若i＜n-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。 h <h i=4 n-2h+1=4 n-h+1=6 20 60 5 31 44 55 65 n-2h+1 i n-h+1

问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ②若i＜n-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。 算法描述： if (i＜n-h+1) Merge (r, r1, i, i+h-1, n);

设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： 问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ③若i≥n-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。 h 20 60 5 31 44 55 65 15 28 i=9 n-h+1=8 n-h+1 i

问题2：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ③若i≥n-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。 算法描述： if (i>=n-h+1) for (k=i; k<=n; k++) r1[k]=r[k];

一趟归并排序算法 void MergePass (int r[ ], int r1[ ], int n, int h) { i=1; while (i≤n-2h+1) //情况1 Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; } if (i＜n-h+1) Merge (r, r1, i, i+h-1, n); //情况2 else for (k=i; k<=n; k++) //情况3 r1[k]=r[k];

问题3：如何控制二路归并的结束？ 解决方法： 开始时，有序序列的长度h=1，结束时，有序序列的长度h=n，用有序序列的长度来控制排序的结束。

问题3：如何控制二路归并的结束？ 算法描述： void MergeSort (int r[ ], int r1[ ], int n ) { h=1; while (h<n) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); }

二路归并排序算法的性能分析 时间性能： 空间性能： 一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，并把结果存放到r1[1]~r1[n]中，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。这是归并排序算法的最好、最坏、平均的时间性能。 空间性能： 算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。

各种排序方法的比较 对排序算法应该从以下几个方面综合考虑： ⑴时间复杂性； ⑵空间复杂性； ⑶稳定性； ⑷算法简单性； ⑸待排序记录个数n的大小； ⑹记录本身信息量的大小； ⑺关键码的分布情况。

各种排序方法的比较 时间复杂度比较 排序方法 平均情况 最好情况 最坏情况 直接插入排序 O(n2) O(n) 希尔排序 O(nlog2n) 冒泡排序 O (n) 快速排序 简单选择排序 堆排序 O (nlog2n) 归并排序

各种排序方法的比较 空间复杂度比较 排序方法 辅助空间 直接插入排序 O(1) 希尔排序 冒泡排序 快速排序 O(log2n) ~O(n) 简单选择排序 堆排序 归并排序 O(n)

稳定性比较 所有排序方法可分为两类， （1）一类是稳定的，包括直接插入排序、冒泡排序、直接选择排序和归并排序； （2）另一类是不稳定的，包括希尔排序、快速排序和堆排序。

算法简单性比较 从算法简单性看， （1）一类是简单算法，包括直接插入排序、直接选择排序和冒泡排序， （2）另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。

待排序的记录个数比较 从待排序的记录个数n的大小看，n越小，采用简单排序方法越合适，n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。

记录本身信息量比较 记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。 排序方法 最好情况 最坏情况 平均情况 直接插入排序 O(n) O(n2) 冒泡排序 直接选择排序

关键码的分布情况比较 当待排序记录按关键码有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

关键码的分布情况比较 当待排序记录按关键码有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。