第10章 排序 排序的基本概念 插入排序 选择排序 交换排序归并排序 基数排序 性能比较 主要知识点

10.1 排序的基本概念 排序是对数据元素序列建立某种有序排列的过程,是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字;不满足主关键字定义的关键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序。 外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。

比较排序算法优劣的标准: (1)时间复杂度:它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度 :算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B的 先后次序保持不变，则称这种排序算法是稳定的

10.2插入排序 插入排序的基本思想是：每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。 常用的插入排序有直接插入排序和希尔排序两种。 1.直接插入排序 其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。

算法如下： void InsertSort (DataType a[], int n) //用直接插入法对a[0]--a[n-1]排序 { int i, j; DataType temp; for(i=0; i<n-1; i++) { temp = a[i+1]; j = i; while(j > -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp;

算法分析: (1)时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) (2)空间效率：仅占用1个附加内存单元——O(1) (3)算法的稳定性：稳定

直接插入排序过程 {64} 7 89 6 24 {5 64 } 64} 89} 5 初始关键字序列: 第一次排序: 第二次排序: 第三次排序: 第四次排序: 第五次排序: 直接插入排序过程

2.希尔(shell)排序(又称缩小增量排序) (1)基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。 (2)技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。 (3)优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。

算法如下： void ShellSort (DataType a[], int n, int d[], int numOfD) //用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值 { int i, j, k, m, span; DataType temp;   for(m = 0; m < numOfD; m++) //共numOfD次循环 { span = d[m]; //取本次的增量值 for(k = 0; k < span; k++) //共span个小组 { //组内是直接插入排序，区别是每次不是增1而是增span for(i = k; i < n-span; i = i+span) { temp = a[i+span]; j = i; while(j > -1 && temp.key < a[j].key) { a[j+span] = a[j]; j = j-span; } a[j+span] = temp;

希尔排序的排序过程 65 34 25 87 12 38 56 46 14 77 92 23 结果序列d=6 结果序列d=3 结果序列d=1 (a) (b) (c) 希尔排序的排序过程

10.3 选择排序 基本思想是：每次从待排序的数据元素集合中选取关键字最小（或最大）的数据元素放到数据元素集合的最前（或最后），数据元素集合不断缩小，当数据元素集合为空时选择排序结束。 常用的选择排序算法： （1）直接选择排序 （2）堆排序

1.直接选择排序 基本思想是：从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟

算法如下： void SelectSort(DataType a[], int n) { int i, j, small; DataType temp;   for(i = 0; i < n-1; i++) { small = i; //设第i个数据元素关键字最小 for(j = i+1; j < n; j++) //寻找关键字最小的数据元素 if(a[j].key < a[small].key) small=j; //记住最小元素的下标 if(small != i) //当最小元素的下标不为i时交换位置 temp = a[i]; a[i] = a[small]; a[small] = temp; }

直接选择排序的排序过程 64 5 7 89 6 24 {5} {5 6} 7} 24} 64} 初始关键字序列: 第一次排序结果: 第二次排序结果: 第三次排序结果: 第四次排序结果: 第五次排序结果: } 最后结果序列: 直接选择排序的排序过程

算法分析 时间效率： O(n2)——虽移动次数较少，但比较次数仍多。 空间效率：O(1)——没有附加单元（仅用到1个temp) 算法的稳定性：不稳定

2.堆排序 基本思想:把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）的数据元素只需比较完全二叉树的高度次，即log2n次，则排序算法的时间复杂度就是O(nlog2n)。 一、堆的定义 堆分为最大堆和最小堆两种。定义如下： 设数组a中存放了n个数据元素，数组下标从0开始，如果当数组下标2i+1<n时有:a[i].key≥a[2i+1].key(a[i].key≤a[2i+1].key)；如果当数组下标2i+2<n时有:a[i].key≥a[2i+2].key (a[i].key≤a[2i+2].key)，则这样的数据结构称为最大堆(最小堆)。

10 50 32 5 76 9 40 88 (a) (b) (a)完全二叉树 (b)最大堆 性质： （1）最大堆的根结点是堆中值最大的数据元素，最小堆的根结点是堆中值最小的数据元素，我们称堆的根结点元素为堆顶元素。 （2）对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递减有序的；对于最小堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递增有序的。

终端结点（即叶子）没有任何子女，无需单独调整 二、 创建堆 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 终端结点（即叶子）没有任何子女，无需单独调整 创建最大堆过程中要多次调用函数：调整完全二叉树中某个非叶结点a[i]（i = (n-1)/2）使之满足最大堆定义，前提条件是该结点的左孩子结点a[2i+1]和右孩子结点a[2i+2]都已是最大堆。函数设计如下：

void CreatHeap (DataType a[], int n, int h) { int i, j, flag; DataType temp;   i = h; // i为要建堆的二叉树根结点下标 j = 2*i+1; // j为i的左孩子结点的下标 temp = a[i]; flag = 0;   while(j < n && flag != 1) { //寻找左右孩子结点中的较大者,j为其下标 if(j < n-1 && a[j].key < a[j+1].key) j++;   if(temp.key > a[j].key) //a[i].key>a[j].key flag=1; //标记结束筛选条件 else //否则把a[j]上移 { a[i] = a[j]; i = j; j = 2*i+1; }   a[i] = temp; //把最初的a[i]赋予最后的a[j]

初始化创建最大堆算法如下： 三、堆排序算法 void InitCreatHeap(DataType a[], int n) { int i; for(i = (n-2)/2; i >= 0; i--) CreatHeap(a, n, i); } 三、堆排序算法 堆排序的基本思想是：循环执行如下过程直到数组为空：（1）把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换；（2）最大堆元素个数减1；（3）由于第（1）步后根结点不再满足最大堆的定义，所以调整根结点使之满足最大堆的定义。

完全二叉树调整为最大堆的过程 10 50 32 5 76 9 40 88 数组 (a)初始状态 (b)调整结点5后 (c)调整结点32后 (d)调整结点50后 (e)调整结点10后 完全二叉树调整为最大堆的过程

堆排序算法如下： void HeapSort(DataType a[], int n) { int i; DataType temp; InitCreatHeap(a, n); //初始化创建最大堆  for(i = n-1; i > 0; i--) //当前最大堆个数每次递减1 { //把堆顶a[0]元素和当前最大堆的最后一个元素交换 temp = a[0]; a[0] = a[i]; a[i] = temp;  CreatHeap(a, i, 0); //调整根结点满足最大堆 }

堆排序算法的排序过程

算法分析： 时间效率：O(nlog2n)。因为整个排序过程中需要调用n-1次堆顶点的调整，而每次堆排序算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。

10.4 交换排序 交换排序的基本思想是：利用交换数据元素的位 置进行排序的方法。 交换排序的主要算法有： 1)冒泡排序 2)快速排序

1.冒泡排序 基本思想：每趟不断将数据元素两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

算法核心语句如下： for(i = 1;i < n && flag == 1; i++) { flag = 0; for(j = 0;j < n - i; j++) if(a[j]. key > a[j+1].key) temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; }

冒泡排序算法的排序过程 初始关键字序列: 第一次排序结果: 第二次排序结果: 第三次排序结果: 第四次排序结果: 第五次排序结果: 最后结果序列: 38 5 19 26 49 97 1 66 [97] [66 97] [49 [38 [26 [19 [5 第六次排序结果: 第七次排序结果: 冒泡排序算法的排序过程

算法分析： 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动数据元素。 最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n) 做了n- i 次关键码比较，执行了n-i 次数据元素交换。此时的比较总次数和记录移动次数为：

2 .快速排序 因此： 时间效率：O（n2) —考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定的 基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快。

算法核心语句如下： while(i < j && temp.key <= a[j].key) j--;//在数组的右端扫描 if(i < j) { a[i] = a[j]; i++; }   while(i < j && a[i].key < temp.key) i++;//在数组的左端扫描 a[j] = a[i]; j--;

快速排序算法一次快速排序过程 60 55 48 37 10 90 84 36 i j 初始关键字序列: (1) (2) (3) (4) (5) (6) (7) (8) 快速排序算法一次快速排序过程

图中标有下划横线的数据元素为本次快速排序选取的标准元素。 初始关键字序列: (1) (2) { 60 55 48 37 10 90 84 36 10} 90} } 55} (3) 最后结果 {37} 快速排序算法各次快速排序过程 图中标有下划横线的数据元素为本次快速排序选取的标准元素。

算法分析： 时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加 空间效率：O(log2n)—因为递归要用堆栈 稳 定 性： 不 稳 定 —因为有跳跃式交换。

10.5 归并排序 归并排序主要是二路归并排序,基本思想是：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。 一次二路归并排序算法如下：

void Merge(DataType a[], int n, DataType swap[], int k) //k为子数组长度，一次二路归并排序后的子序列存于数组swap中 { int m = 0, u1,l2,i,j,u2;   int l1 = 0; //第一个有序子数组下界为0 while(l1+k <= n-1) { l2 = l1 + k; //第二个有序子数组下界 u1 = l2 - 1; //第一个有序子数组上界 u2 = (l2+k-1 <= n-1)? l2+k-1: n-1; //第二个子数组上界 //两个有序子数组合并 for(i = l1, j = l2; i <= u1 && j <= u2; m++) { if(a[i].key <= a[j].key) { swap[m] = a[i]; i++; } else { swap[m]=a[j]; j++; } }

//子数组2已完，将子数组1中剩余的元素存放到swap while(i <= u1) { swap[m] = a[i]; m++; i++; } //子数组1已完，将子数组2中剩余的元素存放到swap while(j <= u2) { swap[m] = a[j]; m++; j++; }   l1 = u2 + 1; }  //将原始数组中只够一组的数据元素顺序存放到数组swap for(i = l1; i < n; i++, m++) swap[m] = a[i]; }

二路归并排序算法分析 时间效率： O(nlog2n) 因为在递归的归并排序算法中，递归调用函数Merge( )约为log2n 次，而每次归并要执行比较约为n次，所以算法总的时间复杂度为O(nlog2n)。 空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列。这是此算法的缺点。 稳定性：稳定

10.6 基数排序 基数排序也称作桶排序，是一种当关键字为整数类型时非常高效的排序方法。 其基本思想是： 10.6 基数排序 基数排序也称作桶排序，是一种当关键字为整数类型时非常高效的排序方法。 其基本思想是： 设待排序的数据元素关键字是m位d进制整数（不足m位的关键字在高位补0），设置d个桶，令其编号分别为0,1,2,…,d-1。首先按关键字最低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；

再对一次基数排序得到的数据元素序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。 数据元素的关键字序列为{710, 342,045, 686, 006, 841, 429, 134, 068, 264} 排序过程如下

841 1 342 2 3 134 264 4 045 5 686 006 6 7 068 8 710 429 9 收集后的新序列: 放置 (a)初始状态 (b)第一次基数排序 (c)第二次基数排序

基数排序算法进出桶中的数据元素序列满足先进先出的原则，桶实际就是队列。实现基数排序算法时，有基于顺序队列和基于链式队列两种不同的实现方法。 在基于链式队列的基数排序算法中，可以把d个队列设计成一个队列数组（设队列数组名为tub），队列数组的每个元素中包括两个域： front域和rear域。front域用于指示队头，rear域用于指示队尾。当第i（i=0,1,2,…,d-1）个队列中有数据元素要放入时，就在队列数组的相应元素tub[i]中的队尾位置插入一个结点。基于链式队列基数排序算法的存储结构示意图如下图所示。

一个十进制关键字K的第i位数值Ki的计算公式为： ... rear front data next ∧ 1 2 d-1 . tub 一个十进制关键字K的第i位数值Ki的计算公式为：

基于链式队列的基数排序算法: #include "LQueue.h" void RadixSort(DataType a[], int n, int m, int d) { int i, j, k, power = 1; LQueue *tub; //把d个队列定义为动态数组 tub = (LQueue *)malloc(sizeof(LQueue )* d); for(i = 0; i < d; i++) QueueInitiate(&tub[i]); //d个队列分别初始化

for(i = 0; i < m; i++) /进行m次放和收 { if(i == 0) power = 1; else power = power *d; for(j = 0; j < n; j++) //放 k = a[j].key /power - (a[j].key /(power * d)) * d; QueueAppend(&tub[k], a[j]);//把a[j]放入第k个队列 } k = 0; for(j = 0; j < d; j++) //回收 while(QueueNotEmpty(tub[j]) != 0) QueueDelete(&tub[j], &a[k]);//从各队列中回收 k++;

基数排序算法分析 特点：不用比较和移动，改用分配和收集，时间效率高！ 时间复杂度为：O (mn)。 空间复杂度：O(n). 稳定性：稳定。(一直前后有序)。

10.7 性能比较 排序方法 最好时 间 平均时间 最坏时间 辅助空间 稳定性 直接插入排序 O(n) O(n2) O(1) 稳定 希尔排序   O(n1.3) 不稳定 直接选择排序 堆排序 O(nlog2n) 冒泡排序 快速排序 O(log2n) 归并排序 基数排序（基于链式队列） O(mn) 基数排序（基于顺序队列） 10.7 性能比较

作业 1) 习题10-1，10-2 ，10-4(1) ，10-20 2) 习题10-4(3)，10-8， 10-9， 10-10 ，10-12 3) 习题10-4(2,4,5)， 10-13，10-17 ， 10-5， 10-6