《数据结构》课程PPT教学课件（2012）第10章 内部排序 10.2 插入排序 10.3 交换排序 10.4 选择排序

第10章内部非序 10.1概述 10.2插入排序 10.3交换排序 10.4选择排序 10.5归并排序 10.6基数排序

1 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 第10章 内部排序

10.2插入排序 边插入边排序，保证子序列中随时都是排好序的。 插入排序有多种具体实现算法： 1)直接插入排序 2)折半插入排序 3)2-路插入排序 小改进 4表插入排序 5)希尔排序 大改进 闪

2 10.2 插入排序 插入排序有多种具体实现算法： 1) 直接插入排序 2) 折半插入排序 3）2-路插入排序 4) 表插入排序 5) 希尔排序 边插入边排序，保证子序列中随时都是排好序的。 小改进 大改进

课堂练习： 以关键字序列(256,301,751,129,937,863,742， 694,076,438)为例，分别写出执行以下算法的各趟排 序结束时，关键字序列的状态，并说明这些排序方法中， 哪些易于在链表（包括各种单、双、循环链表）上实现？ ①直接插入排序 ②希尔排序（取dk=5,3,1) 答：显然，直接插入排序方法易于在链表上实现；但希尔排 序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：

3 课堂练习： 以关键字序列（256，301，751，129，937，863，742， 694，076，438）为例，分别写出执行以下算法的各趟排 序结束时，关键字序列的状态，并说明这些排序方法中， 哪些易于在链表（包括各种单、双、循环链表）上实现？ ① 直接插入排序 ② 希尔排序（取dk=5,3,1） 答：显然，直接插入排序方法易于在链表上实现；但希尔排 序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：

原始序列：256,301,751,129,937,863,742,694,076,438 直 第1趟[256,301]，751,129,937,863,742,694,076,438 第2趟 [256,301,751],129,937,863,742,694,076,438 留 第3趟 [129,256,301,751],937,863,742,694,076,438 第4趟 [129,256,301,751,937],863,742,694,076,438 排 第5趟[129,256,301,751,863,937]，742,694,076,438 第6趟[129,256,301,742,751,863,937]，694,076,438 第7趟[129,256,301,694,742,751,863,937]，076,438 第8趟[076,129,256,301,694,742,751,863,937]，438 第9趟[076,129,256,301,438,694,742,751,863,937]

4 原始序列： 256，301，751，129，937，863，742，694，076，438 [256，301]，751，129，937，863，742，694，076，438 [256，301，751]，129，937，863，742，694，076，438 [129，256，301，751]，937，863，742，694，076，438 [129，256，301，751，937]，863，742，694，076，438 [129，256，301，751，863，937]，742，694，076，438 [129，256，301，742，751，863，937]，694，076，438 [129，256，301，694，742，751，863，937]，076，438 [076，129，256，301，694，742，751，863，937]，438 [076，129，256，301，438，694，742，751，863，937] 第1趟 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟 第8趟 第9趟

原始序列：256,301,751,129,937,863,742,694,076,438 希 第1趟256,301,694,076,438,863,742,751,129,937 dk=5 排 第2趟 076,301,129,256,438,694,742,751,863,937 dk=3 第3趟 076,129,256,301,438,694,742,751,863,937 dk=1 (取dk-5,3,1)

5 原始序列： 256，301，751，129，937，863，742，694，076，438 (取dk=5, 3, 1) 第1趟 256，301，751 694，129 076，937 48，863，742，694 751，076 129，438 97 dk=5 第2趟 dk=3 第3趟 dk=1 256 07，301，694 129，076 25，438，863 694，742，751，129 863，937 076，301 129，129 256，256 301，438，694，742，751，863，937

时间效率：0125)~0(1.6125)—由经验公式得到 空间效率：0(1)— 因为仅占用1个缓冲单元（与算法有关） 算法的稳定性：不稳定— 因为49排序后却到了49的前面 希尔排序算法（主程序） 参见教材P272 void ShellSort(SqList &L,int dlta[,int t) /按增量序列dlta0.t-1对顺序表L作Shel排序 for(k=0 k<t ++k) dk值依次装在dta[t]中 ShellSort(L,dlta[k]); /增量为dtak的一趟插入排序 //ShellSort

6 void ShellSort(SqList &L，int dlta[ ]，int t){ //按增量序列dlta[0.t-1]对顺序表L作Shell排序 for(k=0；k<t；++k) ShellSort(L，dlta[k])； } // ShellSort 时间效率： 空间效率：O（1）——因为仅占用1个缓冲单元(与算法有关） 算法的稳定性：不稳定——因为49*排序后却到了49的前面 希尔排序算法（主程序） 参见教材P272 O(n 1.25）～O（1.6n 1.25）——由经验公式得到 dk值依次装在dlta[t]中 //增量为dlta[k]的一趟插入排序

希尔排序算法（其中某一趟的排序操作） void ShellInsert(SqList &L,int dk){ 参见教材P272 /对顺序表L进行一趟增量为dk的Shel排序，dk为步长因子 for(i=dk+1 i0&&(r[0].key<r[jl.key);j-=dk)r[j+dk]=r[j] /关键字较大的记录在子表中不断后移 r[j+dk]=r[0] /在本趟结束时将插入到正确位置 //if 理解难点：整理动作是二合一的，r0] //ShellInsert 仍是每个dk子集的哨兵，用于子集的彻 底排序」

7 理解难点：整理动作是二合一的， r[0] 仍是每个dk子集的哨兵，用于子集的彻 底排序！ for(i=dk+1；i0&&(r[0].key<r[j].key); j-=dk) r[j+dk]=r[j]； r[j+dk]=r[0]； }//if } //ShellInsert void ShellInsert(SqList &L，int dk) { 希尔排序算法（其中某一趟的排序操作） 参见教材P272 //对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子 //开始将r[i] 插入有序增量子表 //暂存在r[0] ，此处r[0]仍是哨兵 //关键字较大的记录在子表中不断后移 //在本趟结束时将r[i]插入到正确位置

对前页程序中间for循环的理解： 空间效率与算法设计有关 for(i=dk+1 i0&&(r[0].key<r[jl.key);j-=dk)r[j+dk]=r[jl r[j+dk]=r[0] 如果没有此句，就只能实现相临的两个数之间的比较，而不 能两两都比较到，所以有可能达不到排序的目的。 例如当dk=5时，第一趟比较之前的原始子集是： 5 7 4 i=1 i+dk=6 i+2dk=11 如果不用for循环，比较的结果是5,4,7 只有执行fo循环后，比较结果才会是4,5,7

8 对前页程序中间for循环的理解： 如果没有此句，就只能实现相临的两个数之间的比较，而不 能两两都比较到，所以有可能达不到排序的目的。 例如当dk=5时，第一趟比较之前的原始子集是： for(j=i-dk; j>0&&(r[0].key<r[j].key); j-=dk) r[j+dk]=r[j]； r[j+dk]=r[0]；} 5 7 4 i=1 i+dk=6 i+2dk=11 如果不用for循环，比较的结果是 5，4，7 只有执行for循环后，比较结果才会是 4，5，7 for(i=dk+1；i<=L.length； ++ i) if(r[i].key < r[i-dk].key) { r[0]=r[i]； 大者后移 空间效率与算法设计有关

10.3交换排序 交换排序的基本思想是： 两两比较待排序记录的关键码，如果发生逆序 (即排列顺序与排序后的次序正好相反)，则交换之， 直到所有记录都排好序为止。 交换排序的主要算法有： 1)冒泡排序 2)快速排序 区

9 10.3 交换排序 两两比较待排序记录的关键码，如果发生逆序 （即排列顺序与排序后的次序正好相反），则交换之， 直到所有记录都排好序为止。 交换排序的主要算法有： 1) 冒泡排序 2) 快速排序 交换排序的基本思想是：

1)冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大” (或“前大后小”)规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列T=(21,25,49,25*,16,08),请写出 冒泡排序的具体实现过程。 初态：21,25,49,25*，16， 08 第1趟21,25,25*，16,08,49 第2趟21,25,16,08,25*，49 第3趟21,16,08,25,25*，49 第4趟16,08,21， 25, 25*,49 第5趟08,16,21,25， 25*,49 区 10

10 1) 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大” （或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列 T=(21，25，49，25* ，16，08），请写出 冒泡排序的具体实现过程。 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 初态： 第1趟 第2趟 第3趟 第4趟 第5趟