第十章 内部排序.

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

1 第十章 内部排序

2 §10.1 概述 §10.2 插入排序 §10.3 交换排序 §10.4 选择排序 §10.5 归并排序 §10.6 基数排序 §10.7 各种排序方法的比较

3 § 概 述 一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

4 一、什么是排序？ 　排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

5 一般情况下， 假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ： 　 Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序。

6 二、内部排序和外部排序 反之，若参加排序的记录数量很大， 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
　若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 　 　 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。

7 三、内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 有序序列区 无 序 序 列 区 经过一趟排序 有序序列区
　　内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 有序序列区 无 序 序 列 区 经过一趟排序 有序序列区 无 序 序 列 区

8 基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：
　基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型： 插入类 直接插入、折半插入、表插入排序、希尔排序 交换类 冒泡排序、快速排序 选择类 简单选择排序、堆排序 归并类 2-路归并排序 其它方法 基数排序

9 待排记录的数据类型定义如下: #define MAXSIZE 1000 // 待排顺序表最大长度
typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; // 顺序表长度 } SqList; // 顺序表类型

10 排序基本操作： 排序算法的时间效率： 比较两个关键字大小 将记录从一个位置移动到另一个位置 简单的排序方法：T(n)=O(n²)
先进的排序方法：T(n)=O(nlog2n) 基数排序：T(n)=O(d.n)

11 §10.2 插 入 排 序 一趟直接插入排序的基本思想： 有序序列R[1..i-1] 无序序列 R[i..n] R[i]
§10.2 插 入 排 序 一趟直接插入排序的基本思想： 有序序列R[1..i-1] 无序序列 R[i..n] R[i] 有序序列R[1..i] 无序序列 R[i+1..n] 每次将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上。

12 1．在R[1..i-1]中查找R[i]的插入位置，
实现“一趟插入排序”可分三步进行： 1．在R[1..i-1]中查找R[i]的插入位置， R[1..j].key  R[i].key < R[j+1..i-1].key； 2．将R[j+1..i-1]中的所有记录均后移 一个位置； 3．将R[i] 插入(复制)到R[j+1]的位置上。

13 直接插入排序（基于顺序查找） 折半插入排序（基于折半查找） 表插入排序（基于链表存储） 希尔排序（基于逐趟缩小增量）
不同的具体实现方法导致不同的算法描述 直接插入排序（基于顺序查找） 折半插入排序（基于折半查找） 表插入排序（基于链表存储） 希尔排序（基于逐趟缩小增量）

14 一、直接插入排序 利用 “顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置” 例 初始 ( )
初始 ( ) i= ( ) i= ( ) i= ( ) i= ( ) i= ( ) 27 i= ( ) 27 27 27 38 49 65 76 97 j j j j j j ( ) 排序结果：

15 算法的实现要点： j 从R[i-1]起向前进行顺序查找， 监视哨设置在R[0]； R[0] = R[i]; // 设置“哨兵”
j=i-1 插入位置 R[0] = R[i]; // 设置“哨兵” for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找 循环结束表明R[i]的插入位置为 j +1

16 对于在查找过程中找到的那些关键字不小于R[i].key的记录，在查找的同时实现记录向后移动；
for (j=i-1; R[0].key<R[j].key; --j); R[j+1] = R[j] R[0] R[i] j j= i-1 插入位置 上述循环结束后可以直接进行“插入”

17 令 i = 2，3，…, n, 实现整个序列的排序。 for ( i=2; i<=n; ++i ) if (R[i].key<R[i-1].key) { 在 R[1..i-1]中查找R[i]的插入位置; 插入R[i] ; }

18 for ( i=2; i<=L.length; ++i )
void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { } } // InsertSort L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置

19 内部排序的时间分析： 实现内部排序的基本操作有两个： （1）“比较”序列中两个关键字的 大小； （2）“移动”记录。

20 对于直接插入排序： “比较”的次数： “移动”的次数： “比较”的次数： “移动”的次数： 最好的情况（关键字在记录序列中顺序有序）：
最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： “移动”的次数：

21 二、折半插入排序 因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。

22 void BiInsertionSort ( SqList &L ) {
} // BInsertSort for ( i=2; i<=L.length; ++i ) { } // for L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] 在 L.r[1..i-1]中折半查找插入位置； for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入

23 low = 1; high = i-1; while (low<=high) { } m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区

24 插入 位置 例如: i L.r low high low low high m m 插入 位置 m 再如: i L.r low high low high high m m m

25 三、表插入排序 为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序过 程中采用的存储结构。利用静态链表
进行排序，并在排序完成之后，一次 性地调整各个记录相互之间的位置， 即将每个记录都调整到它们所应该在 的位置上。

26 例：关键字序列 T=(21，25，49，25*，16，08）， 请写出表插入排序的具体实现过程。
解：假设该序列（结构类型)已存入一维数组SL[7]中，将SL[0]作为表头结点。则算法执行过程为： 指向第1个元素 i 关键字 SL[i].key 指针 SL[i].link MaxNum 1 21 2 25 3 49 4 25* 5 16 6 08 初态 1 5 6 i=1 2 i=2 4 3 i=3 i=4 3 i=5 1 i=6 5

27 void LInsertionSort (Elem SL[ ]， int n){
// 对记录序列SL[1..n]作表插入排序 SL[0].key = MAXINT ; SL[0].next = 1; SL[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL[0].next;SL[k].key<= SL[i].key ; j=k, k=SL[k].next ) { SL[j].next = i; SL[i].next = k; } // 结点i插入在结点j和结点k之间 }// LinsertionSort

28 如何在排序之后调整记录序列？ 算法中使用了三个指针： 其中：p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置

29 void Arrange ( Elem SL[ ], int n ) { p = SL[0].next; // p指示第一个记录的当前位置
for ( i=1; i<n; ++i ) { while (p<i) p = SL[p].next; q = SL[p].next; // q指示尚未调整的表尾 if ( p!= i ) { SL[p]←→SL[i]; // 交换记录，使第i个记录到位 SL[i].next = p; // 指向被移走的记录 } p = q; // p指示尚未调整的表尾， // 为找第i+1个记录作准备 } // Arrange

30 四、希尔排序（又称缩小增量排序） 基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 技巧：子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短(例如依次取5,3,1),直到dk＝1为止。 优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。

31 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。
将记录序列分成若干子序列，分别对每个子序列进行插入排序。 例如：将 n 个记录分成 d 个子序列： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] } 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。

32 例如： 第一趟希尔排序，设增量 d =5 第二趟希尔排序，设增量 d = 3 第三趟希尔排序，设增量 d = 1

33 void ShellInsert ( SqList &L, int dk ) {
for ( i=dk+1; i<=n; ++i ) if ( L.r[i].key< L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j>0&&(L.r[0].key<L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if } // ShellInsert

34 void ShellSort (SqList &L, int dlta[], int t)
for (k=0; k<t; ++t) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 } // ShellSort

35 §10.3 交换 排 序 一、起泡排序 二、一趟快速排序 三、快速排序 四、快速排序的时间分析

36 假设在排序过程中，记录序列R[1..n]的状态为：
一、起泡排序 　　假设在排序过程中，记录序列R[1..n]的状态为： n-i+1 无序序列R[1..n-i+1] 有序序列 R[n-i+2..n] 比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上 第 i 趟起泡排序 无序序列R[1..n-i] 有序序列 R[n-i+1..n]

37 例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。
初态： 第1趟 第2趟 第3趟 第4趟 第5趟 21，25，49， 25*，16， 08 21，25，25*，16， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49 每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；

38 void BubbleSort(Elem R[ ], int n) {
while (i >1) { } // while } // BubbleSort i = n; if (R[j+1].key < R[j].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } //if lastExchangeIndex = 1; for (j = 1; j < i; j++) i = lastExchangeIndex; // 本趟进行过交换的 // 最后一个记录的位置

39 2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。
注意: 1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。 2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。 例如: 2 3 5 1 3 5 1 5 7 9 8 9 i=2 i=6 i=7 for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …

40 n-1 时间分析: “比较”的次数： “移动”的次数： “比较”的次数： “移动”的次数： 最好的情况（关键字在记录序列中顺序有序）：
只需进行一趟起泡 “比较”的次数： “移动”的次数： n-1 最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡 “比较”的次数： “移动”的次数：

41 二、一趟快速排序（一次划分） 　目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。

42 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字
例如 R[0] s 52 t 23 14 52 80 low low low low low high high high high high high 设 R[s]=52 为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字

43 可见，经过“一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t， 之后逐渐减小 high，增加 low，并保证 R[high].key≥52，和 R[low].key≤52,否则进行记录的“交换”。

44 int Partition (RedType& R[], int low, int high) {
pivotkey = R[low].key; while (low<high) { while (low<high && R[high].key>=pivotkey) --high; R[low]←→R[high]; while (low<high && R[low].key<=pivotkey) ++low; } return low; // 返回枢轴所在位置 } // Partition

45 int Partition (RedType R[], int low, int high) {
R[0] = R[low]; pivotkey = R[low].key; // 枢轴 while (low<high) { } while(low<high&& R[high].key>=pivotkey) -- high; // 从右向左搜索 R[low] = R[high]; while (low<high && R[low].key<=pivotkey) ++ low; // 从左向右搜索 R[high] = R[low]; R[low] = R[0]; return low;

46 三、快速排序 首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。 分别进行快速排序 一次划分
无 序 的 记 录 序 列 一次划分 无序记录子序列(1) 枢轴 无序子序列(2) 分别进行快速排序

47 void QSort (RedType & R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序
if (s < t-1) { // 长度大于1 } } // QSort pivotloc = Partition(R, s, t); // 对 R[s..t] 进行一次划分 QSort(R, s, pivotloc-1); // 对低子序列递归排序，pivotloc是枢轴位置 QSort(R, pivotloc+1, t); // 对高子序列递归排序

48 void QuickSort( SqList & L) { // 对顺序表进行快速排序 QSort(L.r, 1, L.length);
第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。 void QuickSort( SqList & L) { // 对顺序表进行快速排序 QSort(L.r, 1, L.length); } // QuickSort

49 四、快速排序的时间分析 假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间：
T(n) = Tpass(n) + T(k-1) + T(n-k) 　其中 Tpass(n)为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。

50 由此可得快速排序所需时间的平均值为： 设 Tavg(1)≤b 则可得结果： 结论: 快速排序的时间复杂度为O(nlogn)

51 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。
为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即： 先对 R(s).key, R(t).key 和 R[(s+t)/2].key，进行相互比较，然后取关键字为 “三者之中”的记录为枢轴记录。

52 选择 排 序 简 单 选 择 排 序 堆 排 序

53 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序
从中选出 关键字最小的记录 第 i 趟 简单选择排序 有序序列R[1..i] 无序序列 R[i+1..n]

54 简单选择排序的算法描述如下： void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i<n; ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换

55 移动记录的次数，最小值为 0, 最大值为3(n-1) 。
时间性能分析 　　 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为： 　　移动记录的次数，最小值为 0, 最大值为3(n-1) 。

56 二、堆排序 堆的定义: 堆是满足下列性质的数列{r1, r2, …，rn}： 或 例如: 是小顶堆 不是堆 (小顶堆) (大顶堆)
{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆

57 不 ri r2i r2i+1 若将该数列视作完全二叉树， 则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。 例如: 是堆
12 36 27 65 40 14 34 98 不 是堆 81 73 55 49

58 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。
　堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 例如： { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } 交换 98 和 12 { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 经过筛选 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 }

59 void HeapSort ( HeapType &H ) { // 对顺序表 H 进行堆排序
for ( i=H.length/2; i>0; --i ) HeapAdjust ( H.r, i, H.length ); // 建大顶堆 for ( i=H.length; i>1; --i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 }

60 定义堆类型为: typedef SqList HeapType; // 堆采用顺序表表示之 两个问题: 如何“建堆”？ 如何“筛选”？

61 所谓“筛选”指的是，对一棵左/右子树 均为堆的完全二叉树，“调整”根结点 使整个二叉树也成为一个堆。 筛选 堆 堆

62 例如: 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了， 因此，需要对它进行“筛选”。 12 12 81 98 73 81 49
比较 12 81 98 比较 73 81 49 64 73 36 27 40 55 64 12 98 12 98 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了， 因此，需要对它进行“筛选”。

63 void HeapAdjust (RcdType &R[], int s, int m)
{ // 已知 R[s..m]中记录的关键字除 R[s] 之外均 // 满足堆的特征，本函数自上而下调整 R[s] 的 // 关键字，使 R[s..m] 也成为一个大顶堆 } // HeapAdjust rc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 自上而下的筛选过程; } R[s] = rc; // 将调整前的堆顶记录插入到 s 位置

64 if ( j<m && R[j].key<R[j+1].key ) ++j;
// 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较大记录的位置 if ( rc.key >= R[j].key ) break; // 再作“根”和“子树根”之间的比较， // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整 R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整

65 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。
建堆是一个从下往上进行“筛选”的过程。 例如: 排序之前的关键字序列为 40 98 81 55 98 49 49 73 81 73 36 12 36 27 27 98 40 49 81 55 73 64 64 12 12 36 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。

66 因此，堆排序的时间复杂度为O(nlogn)。
堆排序的时间复杂度分析： 1. 对深度为 k 的堆，“筛选”所需进行的关键字 比较的次数至多为2(k-1)； 2. 对 n 个关键字，建成深度为h(=log2n+1)的堆， 所需进行的关键字比较的次数至多 4n； 3. 调整“堆顶” n-1 次，总共进行的关键 字比较的次数不超过 2 (log2(n-1)+ log2(n-2)+ …+log22) < 2n(log2n) 因此，堆排序的时间复杂度为O(nlogn)。

67 § 归 并 排 序 　　归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。

68 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列
　　在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列 有序子序列 R[l..m] 有序子序列 R[m+1..n] 归并为一个记录的有序序列。 有 序 序 列 R[l..n] 这个操作对顺序表而言，是轻而易举的。

69 … … void Merge (RcdType SR[], RcdType &TR[], int i, int m, int n) {
// 将有序的记录序列 SR[i..m] 和 SR[m+1..n] // 归并为有序的记录序列 TR[i..n] } // Merge for (j=m+1, k=i; i<=m && j<=n; ++k) { // 将SR中记录由小到大地并入TR if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } … …

70 if (i<=m) TR[k..n] = SR[i..m];
// 将剩余的 SR[i..m] 复制到 TR if (j<=n) TR[k..n] = SR[j..n]; // 将剩余的 SR[j..n] 复制到 TR

71 归并排序的算法 如果记录无序序列 R[s..t] 的两部分 R[s..(s+t)/2] 和 R[(s+t)/2+1..t]
分别按关键字有序， 则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该先分别对这两部分进行 2-路归并排序。

72 例如： 52, 23, 80, , 68, (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23][80] [36, 68][14] [ 52] [23] [36][68] [ 23, 52] [36, 68] [ 23, 52, 80] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ]

73 … … void Msort ( RcdType SR[], RcdType &TR1[], int s, int t ) {
// 将SR[s..t] 归并排序为 TR1[s..t] if (s= =t) TR1[s]=SR[s]; else { } } // Msort … …

74 m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] Msort (SR, TR2, m+1, t); //递归地SR[m+1..t]归并为有序的TR2[m+1..t] Merge (TR2, TR1, s, m, t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

75 void MergeSort (SqList &L) {
MSort(L.r, L.r, 1, L.length); } // MergeSort 　容易看出，对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。

76 § 基 数 排 序

77 　基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。
多关键字的排序 链式基数排序

78 一、多关键字的排序 n 个记录的序列 { R1, R2, …，Rn} 对关键字 (Ki0, Ki1,…,Kid-1) 有序是指：
对于序列中任意两个记录 Ri 和 Rj (1≤i<j≤n) 都满足下列(词典)有序关系： (Ki0, Ki1, …,Kid-1) < (Kj0, Kj1, …,Kjd-1) 其中: K0 被称为 “最主”位关键字 Kd-1 被称为 “最次”位关键字

79 实现多关键字排序 通常有两种作法: 最高位优先MSD法 最低位优先LSD法

80 最高位优先MSD法 先对K0进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，...…， 依次类推，直至最后对最次位关键字排序完成为止。

81 最低位优先LSD法 先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位关键字 K0 排序完成为止。
排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。

82 系别、班号和班内的序列号，其中以系别为最主位关键字。
　　例如:学生记录含三个关键字: 系别、班号和班内的序列号，其中以系别为最主位关键字。 LSD的排序过程如下: 无序序列 3,2,30 1,2,15 3,1,20 2,3,18 2,1,20 对K2排序 1,2,15 2,3,18 3,1,20 2,1,20 3,2,30 对K1排序 3,1,20 2,1,20 1,2,15 3,2,30 2,3,18 对K0排序 1,2,15 2,1,20 2,3,18 3,1,20 3,2,30

83 二、链式基数排序 　　假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。 　　对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。

84 例如：对下列这组关键字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “个位数” 取值分别为 0, 1, …, 9　 “分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, …, 9 “分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集” 在一起； 最后按其“百位数”重复一遍上述操作。

85 ２．“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同；
　　在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： １．待排序记录以指针相链，构成一个链表； ２．“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同； ３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表; ４．对每个关键字位均重复 2) 和 3) 两步。

86 例如： 进行第一次分配 f[0] r[0] →230← f[7] r[7] →367 ← →167 →237 f[8] r[8] →138←
p→369→367→167→239→237→138→230→139 进行第一次分配 f[0] r[0] →230← f[7] r[7] → ← →167 →237 f[8] r[8] →138← f[9] r[9] → ← →239 →139 进行第一次收集 p→230 →367→167→237 →138 →368→239→139

87 进行第二次分配 f[3] r[3] →230 ← →237 →138 →239 →139 f[6] r[6] →367 ← →167
p→230→367→167→237→138→368→239→139 进行第二次分配 f[3] r[3] → ← →237 →138 →239 →139 f[6] r[6] → ← →167 →368 进行第二次收集 p→230→237→138→239→139 →367→167→368

88 进行第三次分配 进行第三次收集之后便得到记录的有序序列 f[1] r[1] →138 ← →139 →167 f[2] r[2]
p→230→237→138→239→139→367→167→368 进行第三次分配 f[1] r[1] → ← →139 →167 f[2] r[2] → ← →237 →239 f[3] r[3] → ← →368 进行第三次收集之后便得到记录的有序序列 p→138→139→167 →230→237→239 →367→368

89 基数排序的时间复杂度为O(d(n+rd))
其中：分配为O(n) 　 收集为O(rd)(rd为“基”) 　 d为“分配-收集”的趟数

90 §10.7 各种排序方法的比较

91 一、时间性能 1. 平均的时间性能 时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序 时间复杂度为 O(n2)：
1. 平均的时间性能 时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序 时间复杂度为 O(n2)： 直接插入排序、起泡排序和 简单选择排序 时间复杂度为 O(n): 基数排序

92 2. 当待排记录序列按关键字顺序有序时 直接插入排序和起泡排序能达到O(n)的时间复杂度， 快速排序的时间性能蜕化为O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

93 2. 快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；
二、空间性能 指的是排序过程中所需的辅助空间大小 1. 所有的简单排序方法(包括：直接插入、 起泡和简单选择) 和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；

94 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n);
4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。

95 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 排序之前 : { · · · · · Ri(K) · · · · · Rj(K) · · · · · } 排序之后 : { · · · · · Ri(K) Rj(K) · · · · ·· · · · · } 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。

96 例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 ) 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是稳定的; 若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 ) 则称该排序方法是不稳定的。

97 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。
3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 例如 : 对 { 4, 3, 4, 2 } 进行快速排序， 得到 { 2, 3, 4, 4 } 4. 快速排序和堆排序是不稳定的排序方法。

98 四、各排序方法时间复杂性 与空间复杂性的比较
四、各排序方法时间复杂性 与空间复杂性的比较 平均时间 最坏情况 最好情况 辅助空间 插入排序 O(n2 ) O( n ) O( 1 ) 冒泡排序 选择排序 快速排序 O(nlog2n) O(log2n) 堆排序 归并排序 基数排序 O(d(rd+n)) O( rd )

99 IBM兼容PC机上运行MS-DOS操作系统时，各排序算法的运行时间。排序关键字为16位随机数。
10 100 1000 10000 30000 正序 逆序 冒泡 .00233 .2267 22.47 2274.0 20452 828.0 3661.3 插入 .00200 .1833 18.13 1847.0 16544 0.3 3654.0 选择 .00167 .0967 2.17 900.3 8142 快速 .00367 .0500 .63 7.3 24 5.0 5.7 归并 .00700 .0700 .87 10.7 35 8.7 9.0 堆 .00900 .1767 2.67 36.3 122 38.3 34.7 基数 .2433 .2333 2.30 23.3 69 24.7

100 结论 当n较小时，各排序算法花费的时间相差不太大，但堆、基数、归并排序耗时较多 当n较大时，快速排序最优，归并、基数、堆都显示较好性能，冒泡、插入、选择则较差 记录集合的初始状态对选择、基数没有影响，对堆、归并、快速影响不大，对插入排序影响最大，对冒泡也有影响 随着n的增大，性能最优为快速排序(所需存储空间小)，归并、堆、基数都显示较好的性能

101 第十一章 外部排序

102 §11.1 外部排序的方法 §11.2 多路平衡归并的实现 §11.3 置换－选择排序 §11.4 最佳归并树

103 § 外部排序的方法 一、问题的提出 二、外部排序的基本过程

104 一. 问题的提出 １．待排序的记录数量很大，不能一次装入内存，则无法利用前几节 讨论的排序方法 (否则将引起频繁访问内存)；

105 活动头磁盘结构示意图

106 ２．对外存中数据的读/写是以“数据块” 为单位进行的； 读/写外存中一个“数据块”的数据所需要的时间为：
TI/O = tseek + tla + n twm 其中 tseek 为寻查时间(查找该数据块所在磁道) tla 为等待(延迟)时间 n twm 为传输数据块中n个记录的时间。

107 二、外部排序的基本过程 由相对独立的两个步骤组成：
１．按可用内存大小，利用内部排序 方法，构造若干( 记录的) 有序子序列，通常称外存中这些记录有序子序列为 “归并段”； ２．通过“归并”，逐步扩大 (记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。

108 例：设有一个包含4500个对象的输入文件。现用一台其内存至多可容纳750个对象的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳250个对象，这样全部对象可存储在 4500 / 250＝18 个页块中。输出文件也放在磁盘上，用以存放归并结果。 由于内存中可用于排序的存储区域能容纳750 个对象, 因此内存中恰好能存3个页块的对象。 在外归并排序一开始，把18块对象，每3块一组，读入内存。利用某种内排序方法进行内排序, 形成初始归并段, 再写回外存。总共可得到6个初始归并段。然后一趟一趟进行归并排序。

109 两路归并排序的归并树 初始 归并段 第一趟 归并结果 第二趟 归并结果 第三趟 归并结果
R R R R R R6 750 初始 归并段 R R R 第一趟 归并结果 R 第二趟 归并结果 R 第三趟 归并结果

110 若把内存区域等份地分为 3 个缓冲区。其中的两个为输入缓冲区，一个为输出缓冲区，可以在内存中实现 2 路归并。
输入缓冲区 1 输出缓冲区 输入缓冲区 2 若把内存区域等份地分为 3 个缓冲区。其中的两个为输入缓冲区，一个为输出缓冲区，可以在内存中实现 2 路归并。 首先, 从参加归并排序的两个输入归并段 R1 和 R2 中分别读入一块，放在输入缓冲区1和输入缓冲区2中。然后，在内存中进行2路归并，归并出来的对象顺序存放到输出缓冲区中。

111 例如：假设有一个含10,000个记录的磁盘 文件，而当前所用的计算机一次只 能对1000个记录进行内部排序，则 首先利用内部排序的方法得到10个 初始归并段，然后进行逐趟归并。 假设进行2路归并(即两两归并)，则 第一趟由10个归并段得到5个归并段； 第二趟由 5 个归并段得到3个归并段； 第三趟由 3 个归并段得到2个归并段； 最后一趟归并得到整个记录的有序序列。

112 分析上述外排过程中访问外存(对外 存进行读/写)的次数： 假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。 则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。

113 由此，对上述例子而言， 1)求得10个初始归并段需访问外存100次； 2)每进行一趟归并需访问外存100次；
3)总计访问外存  100 = 500次。

114 外排总的时间还应包括内部排序 所需时间和逐趟归并时进行内部归并 的时间，显然，除去内部排序的因素 外，外部排序的时间取决于逐趟归并
所需进行的“趟数”。 例如，若对上述例子采用5路归并， 则只需进行2趟归并，总的访问外存的 次数将压缩到  100 = 300 次。

115 一般情况下，假设待排记录序列 含 m 个初始归并段，外排序时采用 k路 归并，则归并趟数为 logkm，显然，
减少，因此对外排序而言，通常采用多 路归并且尽可能减小初始归并段的个数。 k 的大小可选，但需综合考虑各种因素。

116 §11.2 多路平衡归并的实现 令u个记录分布在k个归并段上，而从k个归并段中要经过k-1次比较才能得到归并后的有序段中的一个记录。因此要得到含u个记录的归并段需进行(u-1)(k-1)次比较。

117 在外排序中，内部归并过程中所需进行关键字比较总次数为：
随着k的增长而增长，从而使内部归并时间随k的增长而增加，从而抵消由于k的增加而减少的读写外存所需的时间。

118 败者树可以使得从k个记录中选出关键字最小的记录仅需进行
次比较。 上式与k无关，不会随着k的增长而增长

119 什么是败者树？ 在双亲结点中记下左右孩子结点中的败者，而让胜者去参加更高一层的比赛。 5-路归并败者树ls[0..4] 冠军 ls[0] 3
1 ls[3] 2 ls[4] b0 b1 b2 4 10 9 20 b3 b4 10 15 16 9 18 20 20 22 40 6 12 6 15 25 12 37 48 5-路归并败者树ls[0..4]

120 败者树的归并过程 冠军 ls[0] 3 ls[1] ls[2] 1 ls[3] 2 ls[4] b0 b1 4 10 9 20 b3 b4
ls[4] b0 b1 4 10 9 20 b3 b4 10 15 16 9 18 20 20 22 40 6 12 6 15 25 12 37 48

121 typedef int LoserTree[k];
败者树的C 语言类型描述如下: typedef int LoserTree[k]; typedef struct { KeyType key; } ExNode, External[k+1];

122 while(b[ls[0]].key!= MAXKEY)){
void K_Merge(LoserTree &ls, External &b){ //利用败者树ls将编号从0到k-1的k个输入归并段 中的记录归并到输出归并段。b[0]至b[k-1]为败者 树上的k个叶子结点，分别存放k个输入归并段中 的当前记录。 for(i = 0; i <k; ++i) input(b[i].key); CreateLoserTree(ls); while(b[ls[0]].key!= MAXKEY)){ q = ls[0]; output(q); input(b[q].key, q); Adjust(ls, q); }// while output(ls[0]); }// K_Merge

123 void Adjust(LoserTree &ls, int s){
//沿从叶子结点b[s]到根结点ls[0]的路径 //调整败者树 t = (s+k)/2; while(t > 0){ if( b[s].key > b[ls[t]].key) s ↔ ls[t]; //s指示新的胜利者 t = t/2; }// while ls[0] = s; }// Adjust

124 void CreatLoser(LoserTree &ls){
//已知b[0]到b[k-1]为完全二叉树ls的叶结点 //存有k个关键字，沿从叶子到根的k条路径 //将ls调整为败者树。 b[k].key = MINKEY; //MINKEY为关键字 //设置ls中败者的初值 for(i = 0; i < k; ++i) ls[i] = k; //依次从b[k-1],b[k-2],…,b[0]出发调整败者 for(i = k-1; i >= 0; --i) Adjust(ls, i); }// CreatLoser

125 §11.3 置换－选择排序 归并趟数与k和m的关系： m的减少也能有效减少归并的趟数s 利用内部排序方法获得的长度相等的初始归并段的个数为：
§11.3 置换－选择排序 归并趟数与k和m的关系： m的减少也能有效减少归并的趟数s 利用内部排序方法获得的长度相等的初始归并段的个数为： 受到内存工作区大小的限制

126 例：已知初始文件含有24个记录，其关键字分别为51,49,39,46,38,29,14,61,15,30,1,48, 52,3,63,27,4,13,89,24,46,58,33,76。假设内存工作区可容纳6个记录，则利用内部排序方法可得4个初始归并段： RUN1：29,38,39,46,49,51 RUN2：1,14,15,30,48,61 RUN3：3,4,13,27,52,63 RUN4：24,33,46,58,76,89

127 若利用置换－选择排序进行排序，则可求得以下3个初始归并段：
RUN1：29,38,39,46,49,51,61 RUN2：1,3,14,15,27,30,48,52,63,89 RUN3：4,13,24,33,46,58,76

128 置换－选择排序的操作过程 (1)从FI输入w个记录到工作区WA； (2)从WA中选出其中关键字最小的记录，记为MINIMAX记录；
设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，可容纳w个记录。排序的操作步骤如下： (1)从FI输入w个记录到工作区WA； (2)从WA中选出其中关键字最小的记录，记为MINIMAX记录； (3)将MINIMAX记录输出到FO中去；

129 (4)若FI不空，则从FI输入下一个记录到WA中；
(5)从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录； (6)重复(3)~(5)，直至在WA中选不出新的MINIMAX记录为止，从而得到一个初始归并段，并输出一个归并段结束标志到FO中去； (7)重复(2)~(6)，直至WA为空。

130 FO WA FI 空 51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,… 51,49,39,46,38,29 14,61,15,30,1,48,52,3,63,27,4,… 29 51,49,39,46,38, 51,49,39,46,38,14 61,15,30,1,48,52,3,63,27,4,… 29,38 51,49,39,46, ,14 51,49,39,46,61,14 15,30,1,48,52,3,63,27,4,… 29,38,39 51,49, ,46,61,14 51,49,15,46,61,14 30,1,48,52,3,63,27,4,… 29,38,39,46 51,49,15, ,61,14 51,49,15,30,61,14 1,48,52,3,63,27,4,… 29,38,39,46,49 51, ,15,30,61,14 51,1 ,15,30,61,14 48,52,3,63,27,4,… 29,38,39,46,49,51 ,1 ,15,30,61,14 48,1,15,30,61,14 52,3,63,27,4,… 29,38,39,46,49,51,61 48,1,15,30, ,14 48,1,15,30,52,14 3,63,27,4,… 29,38,39,46,49,51,61,* 29,38,39,46,49,51,61,*,1 48, ,15,30,52,14 48,3,15,30,52,14 63,27,4,…

131 从上述例子可见，置换－选择排序所得初始归并段的长度是不相等的。
当输入文件中记录的关键字为随机数时，所得初始归并段的平均长度为内存工作区大小w的两倍。 环形路总长l 将落下的雪 路上的积雪 扫雪车前积雪的高度=h

132 §11.4 最佳归并树 初始归并段长度不等对平衡归并有何影响？

133 设有9个初始归并段，其长度分别为9，30，12，18，3，17，2，6，24。现作 3-路平衡归并，其归并树（表示归并过程的图）为：
51 38 32 121 若每个记录占用一个物理块，则两趟归并需要读/写外存的次数为： ( )×2×2 = 484

134 要想使得读写外存的次数尽可能少，需要使得归并树的带权路径长度为最小。
构造赫夫曼树 2 3 6 9 12 17 18 24 11 30 32 59 最佳归并树 121 9，30，12，18，3，17，2，6，24

135 不是最优方案 8个归并段的归并树：9，12，18，3，17，2，6，24 带权路径长度
11 32 59 不是最优方案 91 带权路径长度 = (2+3+6)×3+( )×2 = 193

136 当初始归并段的数目不足时，需附加长度为零的“虚段”，并按构造赫夫曼树的原则来生成最佳归并树。
2 3 6 9 12 17 18 5 20 24 47 带权路径长度 = (2+3+0)×3+( )×2 +24×1= 163 91

137 如何判定附加“虚段”的数目？ 在一般情况下，对k-路归并而言， 若(m - 1)MOD(k - 1) = 0，则无需加虚段；

138 本章学习要点 1. 了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。

139 2. 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。
按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法 和 O(dn)的基数排序方法。

140 3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
4. 了解外部排序的基本过程及其时间分析。