第十章 内部排序.

Presentation on theme: "第十章 内部排序."— Presentation transcript:

1 第十章 内部排序

2 本章内容 讨论和比较各种排序方法：插入排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。
在每类排序方法中，重点讨论性能先进的高效方法(如，交换排序类中的快速排序，选择排序类中的堆排序等)。

3 本章要点 理解各种排序方法的特点，并能加以灵活应用； 了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法；
掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能； 快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。

4 基本概念 排序 定义 排序过程中的两种基本操作
排序又称分类，是计算机中很重要的操作，它是将一个数据元素（或记录）的任意序列排列成一个按关键字有序的序列。 定义 设有记录序列{R1、R2………..Rn}，其相应的关键字序列为{K1、K2………..Kn}； 若存在一种确定的关系：Kx≤Ky≤… ≤Kz，则将记录序列{R1、R2………..Rn}排成按该关键字有序的序列{ Rx、Ry ……….. Rz}的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。 排序过程中的两种基本操作 比较操作：比较两个关键字值的大小的操作。 移动操作：将记录从一个位置移动到另一个位置的操作。

5 基本概念（续） 排序方法 稳定的排序方法 不稳定的排序方法
若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj (1≤i<j≤n)，即排序前Ri在Rj前，若在排序后 Ri仍在Rj前，则称排序是稳定的。 不稳定的排序方法 待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1≤i< j≤n)，即排序前Ri在Rj前，若在排序后Rj却在Ri前，则称排序是不稳定稳定的。

6 基本概念（续） 排序的分类 待排序列的三种存储结构 内部排序 外部排序 顺序存储：存储在地址连续的一组存储单元中（以此为例）；
待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序 外部排序 待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。 待排序列的三种存储结构 顺序存储：存储在地址连续的一组存储单元中（以此为例）； 链式存储：存储在地址不连续的一组存储单元（链表）中； 地址存储：记录顺序存储，另设关键字和记录地址排序。

7 10.1 插入排序 直接插入排序 1 2 3 4 5 36 24 10 6 12 r[0] 用作哨兵。共执行 5 遍操作。
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1 2 3 4 5 36 24 10 6 12 r[0] 用作哨兵。共执行 5 遍操作。 每遍操作：先将元素复制内容放入r[0]，再将本元素与已排序的序列从尾开始进行比较。在已排序的序列中寻找自己的位置进行插入，或者寻找不到，一直进行到哨兵为止，意味着本元素最小，应该放在 r[1] 。 每进行一遍，排序的序列将增加一个元素。如果序列中有 n 个元素，那么最多进行n 遍即可。

8 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

9 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

10 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

11 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

12 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

13 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

14 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

15 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

16 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

17 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

18 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

19 直接插入排序 1 2 36 24 10 6 12 3 4 5 i

20 直接插入排序 1 2 36 24 10 6 3 4 5 12 i

21 直接插入排序 1 2 36 24 10 6 3 4 5 12 i

22 直接插入排序 1 2 36 24 10 6 3 4 5 12 i

23 直接插入排序 1 2 36 24 10 6 3 4 5 12 i

24 直接插入排序 O(n2) 1 2 10 20 30 40 3 4 5 50 分析: 移动、比较次数可作为衡量时间复杂性的标准
1 2 10 20 30 40 3 4 5 50 O(n2) 分析: 移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 ∑ 1 = n-1 i=2 移动次数 0 n n 逆序时：比较次数 ∑ i = (n+2)(n-1)/2 i=2 移动次数 ∑ (i+1) = (n+4)(n-1)/2 n

25 直接插入排序 一种简单的排序方法 将记录一个个插入到已排序好的有序表中，从而得到长度增加的新的有序表。 void InsertSort ()
{ for (i = 2; i <= n; i++) { r[0] = r[i]; for (j = i - 1; r[0] < r[j]; j--) r[j+1] = r[j]; r[j+1] = r[0]; }

26 插入排序（续） 直接插入排序性能分析 比较次数 移动次数
最好情况 n-1 最坏情况 (n+2)(n-1)/2 平均比较次数 (n+4)(n-1)/4 移动次数 最好情况 2(n-1) 最坏情况 (n+4)(n-1)/2 平均移动次数 (n+8)(n-1)/4 直接插入排序的时间复杂度为 O(n2)。但在待排序列有序的的情况下，直接插入排序的时间复杂度下降为 O(n)。

27 插入排序（续） 折半插入排序 2-路插入排序 表插入排序 与直接插入排序不同之处在于查找插入位置时不是用顺序查找，而是用折半查找。
移动次数与直接插入排序相同，只是比较次数少了，因此其时间复杂度也为 O(n2)。 2-路插入排序 目的：减少排序过程中移动记录的次数； 代价：需要 n 个记录的辅助空间d 将 r[1] 赋值给d[1]，将d 看成循环的，其它记录均与 d[1] 比较，比较小则在 d[1] 前插入，反之则在 d[1] 后插入。 表插入排序 附设指针域，改变指针的值，不移动记录而得到排序结果

28 折半插入排序 36 24 10 6 12 i low high Status InsertSort() {
方法：在已排序的序列中查找下一元素的插入位置，将该元素插入进去，形成更长的排序序列。如： 12 的插入位置为下标 3。 减少了比较次数，未降低时间复杂性。 36 24 10 6 12 high i low Status InsertSort() { for ( i = 2; i <= n ; i++ ) { r[0] = r[i]; low = 1 ; high = i-1 ; while (low <= high) { m = ( low + high ) / 2 ; if (r[0] < r[m]) high = m -1 ; else low = m + 1; } for (j = i - 1; j >= high + 1; j--) r[j+1] = r[j]; r[high+1] = r[0];

29 折半插入排序 36 24 10 6 12 high i low

30 折半插入排序 36 24 10 6 12 25 high i low

31 插入排序（续） 希尔排序－－－“缩小增量排序” 125 32 256 345 12 214 8 452 21 99 618 77 待排序列：
用一定的增量间隔将待排序列分组，每组都采用简单插入排序 排序完一遍后，缩小增量间隔，再对新的分组采用简单插入排序；反复此过程，直至增量间隔为 1 ，即整个待排序列为一组时，执行一遍简单插入排序后结束。 125 32 256 345 12 214 8 452 21 99 618 77 待排序列： 125 32 256 345 12 214 8 452 21 99 618 77 增量为 7 ： 125 452 32 21 32 21 256 99 256 99 345 618 12 77 125 32 256 345 12 214 8 452 21 99 618 77 增量为 5 ： 125 214 618 21 8 77 21 8 77 99 452 345 32 345 32 12 256 125 32 256 345 12 214 8 452 21 99 618 77 增量为 3 ： 125 32 21 256 21 32 125 256 8 12 452 618 99 214 345 77 77 99 214 345 125 32 256 345 12 214 8 452 21 99 618 77 增量为 1 ： 125 32 256 345 12 214 8 452 21 99 618 77 125 32 256 345 12 214 8 452 21 99 618 77 排序结果 ：

32 希尔排序 希尔排序的时间复杂度与增量序列有关，分析起来很复杂，有人认为为 O(n1.5)，也有人认为为 O(n1.3)； 如何选择最佳d序列，目前尚未解决； dlta[k] = 2t-k ≤k≤t≤log2(n-1) dlta[k] = 2t-k+1 0≤k≤t≤log2(n-1) dlta[k]=(3t-k-1)/2 0≤k≤t≤log3(2n+1) 1: 2: 3: 最后一个增量值必须为1 避免增量序列中的值（尤其是相邻的值）有公因子 希尔排序为不稳定排序 希尔排序简单，仅需要一个单元额外的辅助空间，在随机情况和数据有序情况下，对效率几乎没有影响。对于小数据量（几百/几千个数据元素）排序性能稳定并且效率不比其它方法差

33 希尔排序算法 数据存放于r[1]~r[n] void shell_sort () {
for (k = 0; k < T; k++) { dk = delta(k); /* 增量序列函数，如: ……15,7,3,1 */ for (i = dk + 1; i <= n; i++) { rc = r[i]; for (j = i - dk; j > 0 && rc < r[j]; j -= dk) r[j + dk] = r[j]; r[j + dk] = rc; }

34 希尔排序C 语言实现 /* 31,15,7,3,1 … */ void shell_sort(void) {
int t, k, i, j, dk, rc; t = 0; while ((1 << t) < n) t++; for (k = 1; k < t; k++) { dk = (1 << (t - k)) - 1; for (i = dk + 1; i <= n; i++) { if (r[i] < r[i - dk]) { rc = r[i]; for (j = i - dk; j > 0 && rc < r[j]; j -= dk) r[j + dk] = r[j]; r[j + dk] = rc; }

35 10.2 交换排序 起泡排序（冒泡排序） 将相邻两记录一一比较，将关键字较小的记录交换在前面，反复此过程，直到待排序列有序为止。
是一种稳定的排序，时间复杂度为O(n2)。 bubble_sort() /* 数据存于r[1]~r[N] */ { int i, j, flag; for (i = n; i > 1; i--) { flag = 0; for (j = 1; j < i; j++) { if (r[j] < r[j+1]) { swap(r[j], r[j+1]); flag = 1; } if (flag) break;

36 起泡排序 原理: 序列中有n个元素，进行n-1趟(条件满足时可以提前结束) 第1趟，针对r[1～n]元素进行。
…… 第n-1趟，针对 r[1～2]元素进行。 每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换 时间复杂性: 正序时 O(n)，逆序时 O(n2)。平均时间复杂性 O(n2)

37 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 97 76 13 27

38 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 97 76 13 27

39 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 97 76 13 27

40 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 97 76 13 27

41 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 97 76 13 27

42 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

43 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

44 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

45 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

46 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

47 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

48 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 49 38 65 76 97 13 27

49 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

50 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

51 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

52 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

53 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

54 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

55 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

56 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

57 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

58 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

59 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

60 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

61 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

62 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

63 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

64 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

65 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

66 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

67 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

68 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

69 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

70 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

71 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

72 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

73 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

74 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

75 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

76 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

77 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

78 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

79 起泡排序 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 38 49 65 76 13 27 97

80 交换排序（续） 快速排序 分治算法原理 是对起泡排序的改进；
将待排序列第一个元素(枢轴元素)放置到序列中的某个位置，使其前面的所有元素都小于它，后面的所有元素都大于它 分别对枢轴元素前面和后面的两段待排序列采用快速排序方法，直至每一段都只剩下一个元素为止 分治算法原理 分解：将原问题分解为若干子问题； 求解：递归地解各子问题，若子问题规模足够小，则直接求解 组合：将各子问题的解组合成原问题的解；

81 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

82 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

83 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

84 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

85 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

86 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

87 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

88 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

89 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

90 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

91 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

92 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

93 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 49 38 65 97 76 13 27 high low 界点

94 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 27 38 13 65 97 49 76 high low 界点

95 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 27 38 13 65 97 49 76 high low 界点

96 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 27 38 13 65 97 49 76 high low 界点

97 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 27 38 13 65 97 49 76 high low 界点

98 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 27 38 13 65 97 49 76 high low 界点

99 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

100 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

101 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

102 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

103 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

104 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

105 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

106 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

107 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

108 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

109 快速排序 若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。 e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。 13 38 27 65 97 49 76 high low 界点

110 快速排序算法 void QuickSort() { QSort(1, n); }
void QSort (int low, int high) { if (low < high) { pivotloc = Partition(low, high); Qsort(low, pivotloc - 1); Qsort(pivotloc + 1, high); }

111 快速排序算法（续） int Partition(int low, int high) { pivotkey = r[low];
while (low < high) { while (low < high && r[high] >= pivotkey ) high--; r[low] = r[high]; while (low < high && r[low] <= pivotkey ) low++; r[high] = r[low]; } r[low] = pivotkey; return low;

112 快速排序分析 是交换排序方法里最快的一种排序，其时间复杂度为 O(nlogn)；
快速排序是不稳定排序。 栈的深度: 最好情况下为 O(log n) ，最坏情况下为 n 。 每次先对较短子序列排序能降低栈的最大深度到O(log n)

113 简单选择排序 简单选择排序 是一种最简单的排序方法； 每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止。
简单选择排序是不稳定排序，时间复杂度为 O( n2 )。 简单选择排序记录移动次数少 void SelectSort(SqList &L) { for (i=1;i<L.length;i++) { j=SelectMinKey(L,i); if (i!=j) L.r[i] ←→ L.r[j]; }

114 简单选择排序举例 简单选择排序举例 <初态> 49 38 65 97 76 49 13 27
<初态> <第1趟> <第2趟> <第3趟> <第4趟> <第5趟> <第6趟> <第7趟> （每趟排序使有序区增加一个记录）

115 锦标赛排序 树形选择排序 又称为锦标赛排序，是一种按锦标赛思想进行的排序； 排序方法
将相邻记录两两分为一组进行比较，将关键字较小的记录送往上一层，参加与其它组关键字较小记录的比较，两两比较后再送往上层关键字较小记录，反复此过程，直到只剩下一个记录即为关键字最小记录； 将待排序列中该最小记录处置为无穷大，则与其比较过的所有记录按层次逐级比较，直至找到下一个最小记录为止；反复此过程直至序列有序。 树形选择排序除第一次外，每次都走了树的一条分支，故其时间复杂度为 O(n log n)。

116 23   [性能] 除第一次外，每次都走了树的一条分支，故其时间复杂度为O(n log2n)。 [缺陷] 辅助空间较多；需与“无穷大值”进行多余的比较 锦标赛排序 23 38 38 46 40 38 稳定排序 46 38 38  38 40 38  46  46     

117 { { 堆排序 堆排序 或 堆的定义 堆排序思路 n 个元素的序列 {k1,k2,…,kn}当且仅当满足下列关系时，称为堆：
ki≤k2i ki≥k2i i=1,2,…,n/2 ki≤k2i ki≥k2i+1 堆排序思路 建立在树形选择排序基础上 将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素； 将其与序列的最后一个元素交换，将序列长度减一； 再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度； 反复此过程，直至序列长度为一，所得序列即为排序后结果。 { { 或

118 堆排序举例 堆排序举例 待排记录的关键字 {32，12，91，26，74，58，63，85} 堆排序的结果为： {12，26，32，58，63，74，85，91}。 85 26 74 58 63 91 12 32 12 91 58 26 32 74 12 85 74 32 26 32 26 12 26 12 12 26 32 26 85 12 63 12 63 58 58 12 12 58 32 12 74 58 58 63 32 91 85 32 32 91 12 85 12 85 12 74 74 12 63 91 63 32 63 91 32 63 26 85 85 26 12 26 26 12

119 堆排序算法实现 void HeapAdjust(int s, int m) { rc = r[s];
for (j=2 * s; j <= m; j *= 2) { if (j < m && r[j] < r[j+1]) j++; if (rc > r[j]) break; r[s] = r[j]; s = j; } r[s] = rc; void HeapSort(HeapType &H) { for (i = length / 2; i > 0; i--) HeapAdjust(i, length); for (i = length; i > 1; i--) { r[1]←→r[i]; HeapAdjust(1, i - 1);

120 堆排序特点 堆排序需要首先初始化堆(比较次数不超过4n)，然后,每次堆调整，排好一个元素(最多2*堆深度) 对记录数较大的文件很有效
堆排序只需一个辅助空间用于交换，其时间复杂度为 O( nlog n ) 堆排序最坏情况下也是O(nlogn)性能 堆排序是不稳定排序

121 归并排序 归并排序 每次将两个或两个以上的有序表合并成一个较长的有序表，反复此过程，直到最终只剩下一个有序表为止；单个记录即是最初的有序表

122 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

123 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

124 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

125 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

126 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

127 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

128 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

129 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

130 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

131 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

132 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

133 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k

134 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k 至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。

135 归并排序 49 13 65 97 76 7 80 A B C i j k 合并两个已排序的顺序表。
e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。 49 13 65 97 76 7 80 A B C i j k 至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。

136 归并排序算法举例

137 归并排序算法实现 Void Merge(int *SR, int *TR, int i, int m, int n)
// 将 SR[i~m] , SR[m+1~n]归并为 TR[i..n] { for (j=m+1, k=i; i<=m && j<=n; k++) { if ( SR[i] <= SR[j]) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i<=m) TR[k~n] = SR[i~m]; if (j<=n) TR[k~n] = SR[j~n];

138 归并排序算法实现 Void MSort(int *SR, int *TR, int *extra, int s, int t )
{ if (s == t) TR[s] = SR[s]; else { m = (s + t) / 2 ; // 将SR[s..t]分为SR[s..m]和SR[m+1..t] Msort(SR, extra, TR, s, m); // 将SR[s..m]归并为有序的extra[s..m] Msort(SR, extra, TR, m+1, t); // 将SR[m+1..t]归并为有序的extra[m+1..t] Merge(extra, TR, s, m, t); // 将extra[s..m]和extra[m+1..t] 归并到TR[s..t] } Void MergeSort() // 将顺序表 L 进行归并排序 { Msort(r, r, extra, 1, length); }

139 归并排序分析 任何情况时间复杂度O(nlog2n) 空间复杂度O(n),每趟都需要复制所有元素 稳定的排序方法
递归方式书写简单，但是实用性差，需改进成非递归算法。但算法显得不够简洁 很少用于内部排序

140 基数排序 借助多关键字排序的思想对单逻辑关键字进行排序 多关键字排序 如 52 张扑克牌按以下规则排成有序：
3<3<3<3<4<4…<A<A<2<2<2<2 牌点：决定大小的主要因素(3<4<…<10<J<Q<K<A<2)； 花色：<<< ，决定大小的次要因素；只有在牌点相同时，才起作用 牌点为高位关键字，花色为低位关键字，决定元素的大小主要看高位关键字，低位关键字只有在高位关键字相等时才发挥作用。 一般的，设有n个记录序列(R1,R2,…,Rn)，每个记录Ri均含有d 个关键字(Ki1,Ki2,…,Kid)，则称此序列有序是指序列中任意两记录 Ri和Rj(1≤i≤j≤n)满足：(Ki1,Ki2,…,Kid)≤(Kj1,Kj2,…,Kjd)，其中K1称为最高位关键字，Kd称为最低位关键字

141 基数排序（续） MSD法:最高位优先（Most Significant Digit first）
按K1进行排序，得若干子序列，子序列中记录具有相同的K1值 再分别对各子序列按K2进行排序，将分成更多的子序列；反复此过程，直到全部子序列分别按Kd进行了排序 将所有子序列（分层次的）依次联接成一个有序序列 LSD法：最低位优先(Least Significant Digit first) 将待排序列依次按Kd,Kd-1,…,K1进行排序得到有序序列，这种排序方法称为最低位优先法 MSD与LSD的比较 MSD和LSD仅规定排序的关键字顺序，未规定对每种关键字如何排序 MSD在排序时间上要比LSD快些，对排序方法是否稳定没有要求，但操作起来相对复杂，因为序列将被分成若干个子序列 LSD每次均对全部记录进行排序，但除按最高位关键字排序对稳定性没有要求外，其后的所有排序必须是稳定的 LSD 比较容易用多次分配和收集来实现

142 链式基数排序 链式基数排序 基数排序是将关键字看成d个关键字复合而成，即按其基数rd所处位置的权值大小分成高、低位关键字，应用多次分配、收集方法将待排序列排成有序序列。 该方法又称为桶排序(bucket sort)，待排序列用静态链表存储，是用2 rd个指针来作为rd个桶的底和盖指针，每次分配将n个记录按其Ki分配到各个桶中，收集时则按各桶顺序从上到下依次收集

143 链式基数排序举例 待排记录的关键字 {32，12，91，26，74，58，63，85}
待排序列： （ 32，12，91，26，74，58，63，85 ） 分配： | | | | | | | | | | 91 32 63 74 85 26 58 12 收集： （ 91，32，12，63，74，85，26，58 ） 分配： | | | | | | | | | | 12 26 32 58 63 74 85 91 收集： （12，26，32，58，63，74，85，91 ）

144 链式基数排序分析 链式基数排序性能分析 每一趟 d趟总计 辅助空间 n个指针域空间O(n)
分配O(n)， 收集O(rd) d趟总计 O(d*(n+rd)) 辅助空间 n个指针域空间O(n) 队头指针数组f[1..rd]和队尾指针数组e[1..rd], O(rd) 辅助空间复杂度：O(rd+n)

145 内部排序方法的比较 排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性 直接插入 O(n) O(n2) O(n2) O(1) 
排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性 直接插入 O(n) O(n2) O(n2) O(1)  希尔 O(n1.3) O(1)  冒泡 O(n) O(n2) O(n2) O(1)  快速 O(nlog2n) O(nlog2n) O(n2) O(log2n)  简单选择 O(n2) O(n2) O(n2) O(1)  堆 O(nlog2n) O(nlog2n) O(nlog2n) O(1)  归并 O(nlog2n) O(nlog2n) O(nlog2n) O(n)  基数 O(d(rd+n)) O(d(rd+n)) O(d(rd+n)) O(rd+n) 

146 排序方法分析 按平均时间排序方法分为四类 O(n2)、O(nlogn)、O(n1+)、O(n)
快速排序是目前基于比较的内部排序中最好的方法 关键字随机分布时，快速排序的平均时间最短，堆排序次之，但后者所需的辅助空间少 当n较小时，可采用直接插入或简单选择排序，前者是稳定排序，但后者通常记录移动次数少于前者，稳定性没要求时可考虑希尔排序。 当n较大时，应采用时间复杂度为O(nlogn)的排序方法或者基数排序的方法，但后者对关键字的结构有一定要求 当n较大时，为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构（如插入排序、归并排序、基数排序） 快速排序和堆排序难于在链表上实现，可以采用地址排序的方法，之后再按辅助表的次序重排各记录 初态基本按正序排列时，应选用直接插入、希尔、冒泡或随机的快速排序 选择排序方法应综合考虑各种因素（数据量和规律性），也可以综合几种算法

147 思考题 希尔排序，快速排序，堆排序，归并排序，基数排序能够提高排序速度的原因分别是什么？ 快速排序和归并排序的非递归算法。

148 作业(1) 以关键码序列(503, 87, 512, 61, 908, 170, 897, 275, 653, 426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： (1) 直接插入排序 (4) 堆排序 (2) 希尔排序(d[1]=5, d[2]=3, d[3]=1) (5) 归并排序 (3) 快速排序 (6) 基数排序 下列哪些排序算法是稳定排序？ (1)直接插入 (2)希尔 (3)冒泡 (4)快速 (5) 简单选择 (6)堆排序 (7)归并 (8)基数 假设有 n 个值不同的元素存于顺序结构中，要求不经完全排序选出自大至小的前k (k<<n) 个元素，可以采用哪些算法？分析算法的复杂度。 假设有 n 个值不同的元素存于顺序结构中，要求不经完全排序选出第k大的元素。写出该算法。 一个有500K个整数(取值0~2G)的单链表中，设计一种算法排序，排序后单链表中数据升序排列，分析算法的时间复杂度。 设有 n 个值不同的元素存于顺序结构中，问能否用比 2n-3 次少的比较次数找出该序列的最大值和最小值？若能，应如何实现？

149 作业(2) 下列那个序列不是堆？如果不是，调整为堆 使用快速排序方法对一个无头单链表进行排序。
100，83，85，82，70，77，66，60，40，20，10 10，20，40，33，39，82，85，37，99，72，46 99，85，40，77，80，60，66，98，82，10，20 使用快速排序方法对一个无头单链表进行排序。 希尔排序，快速排序和堆排序所需要的辅助空间分别为多少？如果快速排序选择序列的第一个元素作为枢轴元素，那么，在什么条件下快速排序的效率将变得很低？ 写出一个递归算法，判断一个顺序表是否为小根堆。 假设有 n 个整数存于顺序结构r[1]~r[n]中，每个元素的取值只有三种可能:1, 2, 3。给出一种时间复杂度为O(n)的算法进行排序。 写出使用冒泡法对数组中元素r[1]~r[n]排序的算法。冒泡排序提前终止的条件是什么？ 简述快速排序和堆排序的算法思想并分析算法的时间和空间复杂度。 书面完成并提交1，2，4，7，9，12