10.1、基本概念 10.2、插入排序 10.3、快速排序 10.4、选择排序 10.5、归并排序 10.6、基数排序 10.7、讨论

Presentation on theme: "10.1、基本概念 10.2、插入排序 10.3、快速排序 10.4、选择排序 10.5、归并排序 10.6、基数排序 10.7、讨论"— Presentation transcript:

1 10.1、基本概念 10.2、插入排序 10.3、快速排序 10.4、选择排序 10.5、归并排序 10.6、基数排序 10.7、讨论
第十章 内部排序 10.1、基本概念 、插入排序 、快速排序 、选择排序 、归并排序 、基数排序 、讨论

2 8.1 基本概念 术语 记录——结点；文件——线性表 关键码：能够唯一确定结点的一个或若干域。 排序码：作为排序运算依据的一个或若干域。
组合排序码，(主关键码，次关键码) 例：(总分数，数据结构分数，大学英语分数) 排序：将一个数据元素(或记录)的任意序列，重排成一个按排序码有序的序列。即排序码域的值具有不减(或不增)的顺序。

3 排序问题：给定一组记录r1, r2, …rn，其排序码分别为k1, k2, …，kn，将这些记录排成顺序为rs1,rs2,…rsn 的一个序列S，满足条件ks1≤ks2≤…≤ksn 。
稳定与不稳定排序：若记录序列中的任意两个记录 Rx、Ry 的关键字 Kx = Ky；如果在 排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的排序，否则是不稳定的排序。 分类： 内部排序：全部记录都可以同时调入内存进行的排序 外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。

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

5 8.2 插入排序 有序序列R[1..i-1] 无序序列 R[i..n] R[i] 有序序列R[1..i] 无序序列 R[i+1..n]
插入排序的基本思想：共做n趟排序，第i趟排序的过程如下 有序序列R[1..i-1] 无序序列 R[i..n] R[i] 有序序列R[1..i] 无序序列 R[i+1..n]

6 8.2 插入排序 1.直接插入排序（基于顺序查找） 2.折半插入排序（基于折半查找） 3.表插入排序（基于链表存储）
4.希尔排序（基于逐趟缩小增量）

7 8.2 插入排序 插入过程分为两步， 1、在已排好序的表中查找插入位置 2、插入 不同的插入算法的区别在于第一步的不同 1、直接插入排序
　　利用 “顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”

8 8.2 插入排序 从R[i-1]起向前进行顺序查找，监视哨设置在R[0]； R[0] R[i] j j=i-1 插入位置
for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找 循环结束表明R[i]的插入位置为 j +1

9 8.2 插入排序 对于在查找过程中找到的那些关键字不小于[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 插入位置 上述循环结束后可以直接进行“插入”

10 8.2 插入排序 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]; // 插入到正确位置

11 完成! 例2：关键字序列T= （21，25，49，25*，16，08）， 请写出直接插入排序的具体实现过程。
*表示后一个25 例2：关键字序列T= （21，25，49，25*，16，08）， 请写出直接插入排序的具体实现过程。 解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或暂存单元（Temp）。则程序执行过程为： 25* 25* 21 25 49 25* 16 08 暂 存 49 21 25 49 25* 49 49 49 25* 49 49 初态： 08 16 25 08 25 25 21 25 25* 21 16 16 16 08 完成! i=1 i=2 i=3 i=4 i=5 i=6

12 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： “移动”的次数：
直接插入排序算法分析： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： “移动”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： “移动”的次数： 空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：稳定

13 平均的情况：若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。 空间效率：O（1）——因为仅占用1个缓冲单元

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

15 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]; // 插入

16 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; // 插入点在高半区

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

18 折半插入排序的算法分析 时间效率：在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。因此，将 n 个对象用折半插入排序所进行的关键码比较次数为：n*log2n 但是移动次数并未减少，所以排序效率仍为O(n2) 。 空间效率： O（1） 稳定性：稳定 讨论：若记录是链表结构，用直接插入排序行否？折半插入排序呢？ 答：直接插入不仅可行，而且还无需移动元素，时间效率更高！ 但链表无法“折半”！

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

20 静态链表的存储结构 #define SIZE 100 Type struct{ RcdType rc; int next; }SLNode Type struct{ SLNode r[SIZE]; int length; }SLinkListType

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

22 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

23 如何在排序之后调整记录序列？ 算法中使用了三个指针: 其中：p指示第i个记录的当前位置； i指示第i个记录应在的位置；
排序的结果只是求得一个有序链表，但只能进行顺序查找，不能进行随机查找，为了实现折半查找，还需要对纪录进行重新排列。 如何在排序之后调整记录序列？ 算法中使用了三个指针: 其中：p指示第i个记录的当前位置； i指示第i个记录应在的位置； q指示第i+1个记录的当前位置

24 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

25 表插入排序算法分析： ① 时间开销：无需移动记录，只需修改2n次指针值。但由于比较次数没有减少，故时间效率仍为O(n2) 。
② 空间开销：空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。 ③ 稳定性：25和25*排序前后次序未变，稳定。

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

27 将记录序列分成若干子序列，分别对每个子序列进行插入排序。
例如：将 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。

28 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。
r[i] 1 2 3 4 5 6 7 8 9 10 49 38 65 97 76 13 27 49* 55 04 初态： 第1趟 (dk=5) 13 49 38 27 49* 65 55 97 76 04 13 49 27 38 65 49* 97 55 04 76 第2趟 (dk=3) 13 13 27 04 49* 49* 38 55 27 04 49 49 55 38 65 65 97 97 76 76 第3趟 (dk=1) 04 55 13 27 04 49 49* 38 76 65 97 13 27 49* 76 97 算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

29 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

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

31 算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。
时间效率： O(n1.25）～O（1.6n1.25）——经验公式 空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定——因为49*排序后却到了49的前面

32 对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。
Knuth利用大量的实验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

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

34 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; // 本趟进行过交换的 // 最后一个记录的位置

35 注意: 例如: 2 3 5 1 3 5 1 5 7 9 8 9 i=2 i=6 i=7 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) …

36 时间分析: 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数： n-1 “移动”的次数： 最坏的情况：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换。 “比较”的次数： “移动”的次数：

37 2） 快速排序 从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。 基本思想： 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺序存储结构

38 例：关键字序列 T=(21，25，49，25*，16，08），快速排序的算法步骤:
初态： 第1趟： 第2趟： 第3趟： 21， 25， 49， 25*，16， 08 ( )， 16，08 21 ，( ) 25，25*，49 (08)，16，21， 25，(25*，49) 08，16，21，25， 25*，(49) 讨论： 1. 这种不断划分子表的过程，计算机如何自动实现？ 2. “快速排序”是否真的比任何排序算法都快？

39 1.这种不断划分子表的过程，计算机如何自动实现？
编程时： ①每一趟的子表的形成是采用从两头向中间交替式逼近法； ②由于每趟中对各子表的操作都相似，主程序可采用递归算法。 一趟快速排序算法（针对一个子表的操作） int Partition(SqList &L,int low,int high){ //一趟快排 //交换子表 r[low…high]的记录，使支点（枢轴）记录到位，并返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。 r[0]=r[low]; //以子表的首记录作为支点记录，放入r[0]单元 （续下页）

40 pivotkey=r[low].key; //取支点的关键码存入pivotkey变量
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; //返回支点记录所在位置。 }//Partition

41 例2：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过程。
high low pivotkey=21 r[i] 1 2 3 4 5 6 初态 21 25 49 25* 16 08 第1趟 3 21 08 25 16 21 49 25* 16 49 08 25 ( 08 ，16 ） （ 25* ， 49， 25 ） Low=high=3，本趟停止，将支点定位并返回位置信息 25*跑到了前面，不稳定！

42 i=low; j=high;r[0]=r[low]; pivot=r[low].key;
一趟快速排序算法流程图 i=low; j=high;r[0]=r[low]; pivot=r[low].key; i < j i < j &&r[j].key>=pivot --j; r[i] = r[j]; i < j &&r[i].key<=pivot --i; r[j] = r[i]; r[i] = r[0]; return ok; Y N j从高端扫描 寻找小于pivot的元素 i从低端扫描 寻找大于pivot的元素

43 整个快速排序的递归算法： void QSort ( SqList &L, int low, int high ) {
if ( low < high) { pivot = Partition ( L, low, high ); QSort ( L, low, pivot-1); QSort ( L, pivot+1, high ); } //长度>1 //QSort 对顺序表L进行快速排序的操作函数为： void QuickSort ( SqList &L) { QSort (L, 1, L.length ); }

44 例：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。
原始序列： 256，301，751，129，937，863，742，694，076，438 256 第1趟 第2趟 第3趟 第4趟 076 256，301，751，129，937，863，742，694，076，438 129 256 751 301 076，129，256，751，937，863，742，694，301，438 076，129，256，438，301，694，742，694，863，937 751 快速排序 076，129，256，301，301，694，742，751，863，937 076，129，256，438，301，694，742，751，863，937 438 076，129，256，301，438，694，742，751，863，937

45 快速排序算法分析： 快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数（新的low和high）。
可以证明，函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。 最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为 o(log2n)。 如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。 稳 定 性： 不稳定 —因为可选任一元素为支点。

46 讨论2. “快速排序”是否真的比任何排序算法都快？
——基本上是！因为每趟可以确定的数据元素是呈指数增加的！ 设每个子表的支点都在中间（比较均衡），则： 第1趟比较，可以确定1个元素的位置； 第2趟比较（2个子表），可以再确定2个元素的位置； 第3趟比较（4个子表），可以再确定4个元素的位置； 第4趟比较（8个子表），可以再确定8个元素的位置； …… 只需log2n ＋1趟便可排好序。 而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。

47 10.4 选择排序 选择排序有多种具体实现算法： 1) 简单选择排序 2) 锦标赛排序 3) 堆排序
选择排序 基本思想：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。 选择排序有多种具体实现算法： 1) 简单选择排序 2) 锦标赛排序 3) 堆排序

48 思路：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
1）简单选择排序 思路：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 ——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构

49 例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。
原始序列： 21，25，49，25*，16，08 第1趟 第2趟 第3趟 第4趟 第5趟 08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 直接选择排序 时间效率： O(n2)——虽移动次数较少，但比较次数仍多。 空间效率：O（1）——无需任何附加单元！ 算法的稳定性：不稳定——因为排序时，25*到了25的前面。

50 讨论：能否利用（或记忆）首趟的n-1次比较所得信息，从而尽量减少后续比较次数呢？ 能！——锦标赛排序和堆排序！
简单选择排序的算法如下： Void SelectSort(SqList &L ) { for (i=1; i<L.length; ++i){ j = SelectMinKey(L,i); if( i!=j ) r[i] r[j]; } } //SelectSort //对顺序表L作简单选择排序 //选择第i小的记录，并交换到位 //在r[i…L.length]中选择key最小的记录 //与第i个记录交换 讨论：能否利用（或记忆）首趟的n-1次比较所得信息，从而尽量减少后续比较次数呢？ 能！——锦标赛排序和堆排序！

51 2） 锦标赛排序 (又称树形选择排序) 基本思想：与体育比赛时的淘汰赛类似。 首先对 n 个记录的关键字进行两两比较，得到 n/2 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 n/2 个较小者之间再进行两两比较，…，如此重复，直到选出最小关键字的记录为止。 优点：减少比较次数，加快排序速度 缺点：空间效率低 例：关键字序列T= （21，25，49，25*，16，08，63），请给出锦标赛排序的具体实现过程。

52 胜者树 r[1] 第一趟： Winner (胜者) 08 21 08 21 08 63 21 25 49 25* 16 08 63 初态：
注：为便于自动处理，建议每个记录多开两个特殊分量： 第一趟： key otherinfo Index(结点位置编号） Tag（是否参加比较） Winner (胜者) r[1] 08 21 08 胜者树 21 25* 08 63 21 25 49 25* 16 08 63 初态： 补足2k( k=log2n )个叶子结点

53 第二趟： Winner (胜者) r[2] 08 21 63 25* 25 49 16 16 16 16 求次小值16时,只需比较2次，即只比较log2n -1次。 令其Tag＝0,不参与比较

54 第三趟： Winner (胜者) r[3] 16 21 63 25* 25 49 08 21 63 令其Tag＝0,不参与比较

55 第四趟： Winner (胜者) r[4] 08 21 63 25* 25 49 16 25 25 25

56 第五趟： Winner (胜者) r[5] 08 21 63 25* 25 49 16 25* 25*

57 第六趟： Winner (胜者) 08 21 63 25* 25 49 16 49 r[6] 49 49

58 第七趟： Winner (胜者) r[7] 08 21 63 25* 25 49 16 63

59 算法分析： 锦标赛排序构成的树是满(完全）二叉树，其深度为 log2n  +1，其中 n 为待排序元素个数。 时间复杂度O(nlog2n)—n个记录各自比较约log2n次 空间效率O(n）—胜者树的附加内结点共有n’-1个！ 稳定性：稳定 —左右结点相同者左为先

60 3） 堆排序 1. 什么是堆？ 2. 怎样建堆？ 3. 怎样堆排序？ 堆的定义：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 ki ≥ k2i ki ≥ k2i+1 ki ≤ k2i ki ≤ k2i+1 或者 i=1, 2,… n/2

61 如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。

62 例 有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？ 91 85 66 76 58 67 2 3 4 5 6 1 55 7 08 25 46 49 58 67 2 3 4 5 6 1 √ √ （大根堆） （小根堆） （大顶堆） （最大堆） （小顶堆） （最小堆）

63 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。
2. 怎样建堆？ 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 注：终端结点（即叶子）没有任何子女，无需单独调整。

64 例：关键字序列T= (21，25，49，25*，16，08），建大根堆。
为便于理解，先将原始序列画成完全二叉树的形式： 完全二叉树的第一个非终端结点编号必为n/2 !(性质5) 21 25 25* 49 16 08 1 2 3 4 5 6 49 i=3: 49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！ 21 而且21还应当向下比较！！

65 void HeapSort (HeapType &H ) { //H是顺序表，含有H.r[ ]和H.length两个分量
建堆算法(堆排序算法中的第一步） void HeapSort (HeapType &H ) { //H是顺序表，含有H.r[ ]和H.length两个分量 for ( i = length / 2; i >0; - - i ) //把r[1…length]建成大根堆 HeapAdjust(r, i, length ); //使r[i…length]成为大根堆 …… } 这是针对结点 i 的堆调整函数，其含义是：从结点i开始到堆尾为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。

66 针对结点 i 的堆调整函数HeapAdjust如下：
——从结点i开始到当前堆尾m为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。 HeapAdjust(r, i, m ){ current=i; child=2*i; temp=r[i]; while(child<=m){ if ( child<m && r[child].key<r[child+1].key ) child= child+1; if(temp.key>=r[child].key)breack; else { r[current]=r[child]; current= child; child=2* child; } } r[current]=temp; } // HeapAdjust //temp是根，child是其左孩子 //检查是否到达当前堆尾 //让child指向两子女中的大者 //根大则不必调整，结束整个函数 //否则子女中的大者上移 //将根下降到子女位置 //并继续向下整理！ //直到自下而上都满足堆定义，再安置老根

67 3. 怎样进行堆排序？ 关键：将堆的当前顶点输出后，如何将剩余序列重新调整为堆？
方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整，如此反复直至排序结束。

68 例：对刚才建好的大根堆进行排序： 49 25 21 16 08 1 2 3 4 5 6 49 25 21 25* 16 08 初始最大堆
* 初始最大堆 25 25* 16 21 1 3 6 5 4 2 08 49 * 交换 1号与 6 号记录

69 08 25 25* 21 16 49 1 2 3 4 5 6 16 25* 08 25 21 49 1 3 6 5 4 2 25 25* 08 08 25 25* * * 16 25* 交换 1号与 5 号记录 从 1 号到 5 号 重新 调整为最大堆

70 25* 16 08 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 25* * 交换 1 号与 4 号记录 从 1号到 4号 重新 调整为最大堆

71 21 16 25* 08 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 * * 交换 1号与3 号记录 从 1 号到 3号 重新 调整为最大堆

72 16 08 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 * * 交换 1 号与2 号记录 从 1 号到 2 号 重新 调整为最大堆

73 void HeapSort (HeapType &H ) { //对顺序表H进行堆排序
堆排序的算法 void HeapSort (HeapType &H ) { //对顺序表H进行堆排序 for ( i = H.length / 2; i >0; -- i ) HeapAdjust(H,i, H.length ); //初始堆 for ( i = H.length; i > 1; --i) { H.r[1] H.r[i]; //交换，要借用temp HeapAdjust( H, 1,i-1 ); //重建最大堆 } 这是针对结点i 的堆调整函数（也是建堆函数），每次调用耗时O(log2n)

74 基于初始堆进行堆排序的算法步骤： 堆的第一个对象V[0]具有最大的关键码，将V[0]与V[n]对调，把具有最大关键码的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即V[0]位置。 再对调V[0]和V[n-1]，调用对前n-2个对象重新调整，…如此反复，最后得到全部排序好的对象序列。

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

76 10.5 归并排序 基本思想：将两个（或以上）的有序表组成新的有序表。
10.5 归并排序 基本思想：将两个（或以上）的有序表组成新的有序表。 更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n/2 个长度为 2 的子序列；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。 例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。

77 len=1 21 25 25* 93 62 72 08 37 16 54 49 21 25 25* 49 62 93 08 72 16 37 54 len=2 21 25 25* 49 08 62 72 93 16 37 54 len=4 08 21 25 25* 49 62 72 93 16 37 54 len=8 08 16 21 25 25* 37 49 54 62 72 93 len=16 整个归并排序仅需log2n 趟

78 一趟归并排序算法: (两路有序并为一路) void Merge (SR，&TR，i, m, n) { // 将有序的SR[i…m]和SR[m+1…n]归并为有序的TR[i…n] for(k=i , j=m+1; i<=m && j<=n; ++k ) { if ( SR[i]<= SR[j] )TR[k]=SR[i++]; else TR[k]=SR[j++]; // 将SR中记录由小到大地并入TR } 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 } // Merge

79 递归形式的两路归并排序算法: (一路无序变为有序)
void MSort (SR，&TR1，s, t) { // 将无序的SR[s…t]归并排序为TR1[s…t] if ( s==t )TR1[s]=SR[s]; // 当len=1时返回 else { m=(s+t)/2; // 将SR [s…t]平分为SR [s…m]和SR [m+1…t] MSort (SR，&TR2，s, m); // 将SR 一分为二, 2分为4… // 递归地将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] } } // MSort 初次调用时为（L, L, 1, length） 简言之，先由“长”无序变成“短”有序， 再从“短”有序归并为“长”有序。

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

81 10.6 基数排序 (Radix Sort) 基本思想： 借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。
问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？

82 1. 什么是“多关键字”排序？实现方法？ 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色：        面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 则可以先按花色排序，花色相同者再按面值排序 也可以先按面值排序，面值相同者再按花色排序。

83 例2：职工分房该如何排序？ 内大规定：先以总分排序（职称分＋工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口……等等排序。 例3：学生评奖学金如何排序？ 多关键字排序的实现方法通常有两种： 最高位优先法MSD(Most Significant Digit first) 最低位优先法LSD(Least Significant Digit first)

84 例：对一副扑克牌该如何排序？ 若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。 用哪种方法更快些？

85 2. 单逻辑关键字怎样“按位值”排序？ 思路： 设n 个记录的序列为：{V0, V1, …, Vn-1 }，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1, Ki2, …, Kid），则其中的每一个分量Kij ( 1 j  d ) 也可看成是一个关键字。 注1： Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元组； 注2： 每个分量Kij (1  j  d ) 有radix种取值，则称radix为基数。

86 例1：关键码984可以看成是 元组；基数 radix 为 。 例2：关键码dian可以看成是 元组；基 数radix 为 。 3 10 4
例1：关键码984可以看成是 元组；基数 radix 为 。 3 10 例2：关键码dian可以看成是 元组；基 数radix 为 。 4 26

87 讨论：是借用MSD方式来排序呢，还是借用LSD方式？
例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。 法1（MSD）：原始序列：32, 13, , *, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, , 32*, 33 因为有分组，故此算法需递归实现。 法2（LSD）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33 无需分组，易编程实现！

88 计算机怎样实现LSD算法？ 例：T=（02，77，70，54，64，21，55，11），用LSD排序。
①各关键字可视为2元组；②每位的取值范围是：0-9；即基数radix ＝10 。因此，特设置10个队列，并编号为0-9。 1 2 3 4 5 6 7 8 9 10个队列 77 55 64 54 02 11 21 70 1 2 3 4 5 6 7 8 出队后序列 11 55 21 64 54 70 77 02 原始序列 1 2 3 4 5 6 7 8 70 21，11 先对低位扫描 出队 02 下一步 54，64 55 分配过程 收集过程 77 又称散列过程！

89 小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。
77 55 64 54 02 11 21 70 1 2 3 4 5 6 7 8 出队后序列 1 2 3 4 5 6 7 8 9 再次入队 77 70 64 55 54 21 11 02 再次出队后序列 02 11 再对高位扫描 21 再次出队 54，55 再次分配 64 再次收集 70，77 小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。 这种LSD排序方法称为:基数排序

90 针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值,让 j = d, d-1, …, 1，
用链队列来实现基数排序— 链式基数排序 实现思路： 针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值,让 j = d, d-1, …, 1， ① 先“分配”到radix个链队列中去； ② 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； ③ 分别用这种“分配”、“收集”的运算逐趟进行排序； ④ 在最后一趟“分配”、“收集” 完成后，所有记录就按其关键码的值从小到大排好序了。

91 实现以下关键字序列的链式基数排序： 例 T=（614，738，921，485，637， 101，215，530，790，306）
原始序列链表： r[0]→ 614 921 485 637 738 101 215 530 790 306 第一趟分配 （从最低位 i = 3开始排序，f[ ] 是队首指针，e[ ] 为队尾指针） e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 790 101 215 530 921 614 485 306 637 738 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第一趟收集（让队尾指针e[i] 链接到下一非空队首指针f[i+1 ] 即可） r[0]→ 530 790 921 101 614 485 215 306 637 738

92 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
第一趟收集的结果： r[0]→ 530 790 921 101 614 485 215 306 637 738 第二趟分配（按次低位 i = 2 ） e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 738 306 215 637 485 790 101 614 921 530 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第二趟收集（让队尾指针e[i] 链接到下一非空队首指针f[i+1 ] ） r[0]→ 530 790 921 101 614 485 215 306 637 738

93 第二趟收集的结果： r[0]→ 530 790 921 101 614 485 215 306 637 738 第三趟分配（按最高位 i = 1 ） e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 637 790 101 215 306 485 530 614 738 921 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第三趟收集（让队尾指针e[i] 链接到下一非空队首指针f[i+1 ] ） r[0]→ 530 790 921 101 614 485 215 306 637 738 排序结束！

94 2.在radix个队列中，每个队列都要设置两 个指针： int f [radix]指示队头( f[ j ]初始为空）；
如何编程实现？ 先作若干说明： 1. 排序前后的n个记录都用顺序表r[ ]存储，但建议增开n 个指针分量（转为静态链表形式）；这样在记录重排时不必移动数据，只需修改各记录的链接指针即可。 2.在radix个队列中，每个队列都要设置两 个指针： int f [radix]指示队头( f[ j ]初始为空）； int e [radix] 指向队尾（e[ j ]不必单独初始化)； 分配到同一队列的关键码要用链接指针链接起来。 （以上一共增开了n+2 radix个附加指针分量）

95 3. 待排序记录存入r[ ]中， r[0]作为头结点；每个记录都包含key分量、othernifo分量和指针域int next分量。
另外，为能单独表示单关键码key的各位，将key改用向量key[0…d-1]来表示之，这样： 第p个记录的关键码的第i位可表示为：r[p].key[i]; 第p个记录的指针分量可表示为： r[p].next

96 链表基数排序的算法： void RadixSort (&list, int d, int radix ) {
int f[radix], e[radix]; for ( int i = 1; i < n; i++ ) r[i].next=i+1; r[n].next=0; //静态链表初始化，将各记录顺次链接。 int p= 1; //p是链表元素的地址指针 for ( i = d-1; i >= 0; i-- ) { //开始做 d 趟分配/收集, i是key的第i位 for ( int j = 0; j < radix; j++ ) f[j] = 0; //初态＝各队列清空 while ( p!= 0 ) { // 开始将n个记录分配到radix个队列 int k = r[p]. key[i]; //取当前记录之key分量的第 i 位 if ( f[k] == 0) f [k] =p; //若第k个队列空, 此记录成为队首； else r[e[k]].next=p; //若队列不空,链入原队尾元素之后 e[k] =p; //修改队尾指针，该记录成为新的队尾 p= r[p].next; } / / 选下一关键字，直到本趟分配完

97 在此算法中，数组r[n]被反复使用，用来存放原始序列和每趟收集的结果。记录从未移动，仅指针改变。
j = 0; // 开始从0号队列（总共radix个队）开始收集 while ( f [j] == 0 ) j++; //若是空队列则跳过 r[0].next=p = f [j]; //建立本趟收集链表的头指针 int last = e[j]; //建立本趟收集链表的尾指针 for ( k = j+1; k < radix; k++) //逐个队列链接（收集） if ( f [k] ) { //若队列非空 r[last].next=f [k]; last = e[k]; //队尾指针链接 } r[last].next=0; //本趟收集链表之尾部应为0 } // RadixSort 在此算法中，数组r[n]被反复使用，用来存放原始序列和每趟收集的结果。记录从未移动，仅指针改变。

98 基数排序算法分析 特点：不用比较和移动，改用分配和收集，时间效率高！ 假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 则需要radix个队列, 进行d 趟“分配”与“收集”。因此时间复杂度：O ( d ( n+radix ) )。 基数排序需要增加n+2radix个附加链接指针，空间效率低 空间复杂度：O（radix）. 稳定性：稳定。(一直前后有序)。 用途：若基数radix相同，对于记录个数较多而关键码位数较少的情况，使用链式基数排序较好。

99 10.7、各种内部排序方法的比较讨论 排序方法 最好情况 平均时间 最坏情况 辅助存储 稳定性 简单排序 O(n) O(n2) O(1）
快速排序 O(nlgn ) O(nlgn) O(lgn) 不稳定 堆排序 归并排序 O(n） 基数排序 O(d(n+rd)) O(rd) 简单选择 直接插入 折半插入 冒泡

100 讨论：若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？
10.7、各种内部排序方法的比较讨论 讨论：若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？ 对基本有序的情况，可选用堆排序、冒泡排序、归并排序等方法； 在基本无序的情况下，最好选用快速排序、希尔排序。 想一想：能选用折半排序么？

101 10.7、各种内部排序方法的比较讨论 1、 各种方法的时、空优劣 2、 比较法分类的下界：O( n logn )
判定树模型：如下图所示，说明对 a,b,c 进行分类的一棵判定树。当判断条件成立时， 转向左，否则转向右。 a < b yes no b < c a < c yes no yes no a < b < c a < c b < a < c b < c yes no no yes a < c < b c < a < b b < c < a c < b < a 注意：树高代表比较的代价。因此只要知道了树高和结点数 n 的关系，就可以求出 用比较法进行排序时的时间代价。另外，n 个结点的分类序列，其叶子结点 共有 n! 片。

102 10.7、各种内部排序方法的比较讨论 2、 比较法分类的下界：O( n logn )
定理：高为 H 的二叉树，最多具有 2(H-1)片叶子。 证明：H ＝ 1 时，最多 1 片叶子，定理成立。 H ＝ 2 时，最多 2 片叶子，定理成立。 设 H ＝ n-1 时公式成立。则当 H ＝ n 时， 根结点有具有叶子结点最多的高为 n-1 的左 右子树；叶子结点总数为： 2(n-2)×2 ＝ 2(n-1) 公式成立。 推论：具有 N 片叶子的二叉树，高最少为 logN + 1。 或比较次数最少为 logN 。 H = 1 H = 2 H = n 高为 n-1 具有2(n-2) 片叶子 高为 n-1 具有2(n-2) 片叶子 定理：把 n 个不同的结点进行分类的任一判定树的高 度至少为 log(n!) + 1 。 证明： n 个元素的排序序列的总数共有 n! 种，因此在 相应的判定树上至少有 n! 片叶子。根据上述定 理，可证。 推论：用比较的方法对 n 个元素的进行分类。在最坏 情况下至少需要 cnlogn(log(n!)) 次比较， 或 Ω(nlogn)

103 10.7、各种内部排序方法的比较讨论 2、 比较法分类的下界： Ω( n logn )
证明： n 个元素的排序序列的总数共有 n! 种，因此在 相应的判定树上至少有 n! 片叶子。根据上述定 理，可证。 推论：用比较的方法对 n 个元素的进行分类。在最坏 情况下至少需要 cnlogn 次比较， 或 Ω(nlogn) 证明：注意到： n! >= n(n-1) (n-2) …… ( n/2 ) >= (n/2)n/2 ∴ log(n!) >= (n/2 ) log(n/2) >= (n/4)logn ∴ 在最坏情况下至少需要 cnlogn 次比较，即 下界为 Ω(nlogn) 即借助于“比较”进行排序，在最坏的情况下 能达到的最好的时间复杂度为O(nlogn). H = 1 H = 2 H = n 高为 n-1 具有2(n-2) 片叶子 高为 n-1 具有2(n-2) 片叶子 3、 注意： 2介绍的是在比较的前提的下界，并不意味着， 在任何情况下，下界都为 Ω( n logn )

104 本章小结 总的要求：深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程极其依据的原则；掌握各种排序方法的时间复杂度的分析方法；理解排序方法“稳定”或“不稳定”的含义； 本章重点：希尔排序、快速排序、堆排序和归并排序等高效方法的排序。 难点：希尔排序、快速排序、堆排序、归并排序和基数排序的排序。

105 本章作业 书面作业: p61: 10.1题、p62: 10.7题 p65:10.31题 p63: 10.12题 上机作业: 1.实现快速排序
2.实现堆排序