第8章 排序

教学内容 8.1 概述 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.6 外部排序 21 8.1　概述 8.2　插入排序 8.3　交换排序 8.4　选择排序 8.5　归并排序 8.6　基数排序 8.6　外部排序 21 25 49 25* 16 08

教学目标 1. 掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用 2. 熟练掌握直接插入排序、折半插入排序、起泡排序、直接选择排序、快速排序的排序算法及其性能分析 3. 掌握希尔排序、归并排序、堆排序、基数排序的方法及其性能分析 4. 掌握外部排序方法中败者树的建立及归并方法，掌握置换-选择排序的过程和最佳归并树的构造方法。

8.1 概述 1. 什么是排序？ 2. 排序的目的是什么？ 将一组杂乱无章的数据按一定规律顺次排列起来。 ——便于查找！ 存放在数据表中 按关键字排序 2. 排序的目的是什么？ ——便于查找！

3. 什么叫内部排序？什么叫外部排序？ 若待排序记录都在内存中，称为内部排序； 若待排序记录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

4.排序算法的好坏如何衡量？ 时间效率——排序速度（比较次数与移动次数） 空间效率——占内存辅助空间的大小 稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

记录序列以顺序表存储 # define MAXSIZE 20 //设记录不超过20个 typedef int KeyType ; //设关键字为整型量（int型） Typedef struct { //定义每个记录（数据元素）的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RedType ; Typedef struct { //定义顺序表的结构 RedType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ;

排序算法分类 规则不同 时间复杂度不同 插入排序 交换排序 选择排序 归并排序 简单排序O(n2) 先进排序O( nlog2n )

8.2 插入排序 基本思想： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 即边插入边排序，保证子序列中随时都是排好序的

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

直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 例（13，6，3，31，9，27，5，11） 【13】, 6, 3, 31, 9, 27, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】

完成! （21，25，49，25*，16，08） *表示后一个25 将序列存入顺序表L中，将L.r[0]作为哨兵 25* 25* 21 25 0 1 2 3 4 5 6 暂 存 21 25 49 25* 49 49 49 25* 49 49 初态： 08 16 08 25 25 21 25 25* 16 21 16 16 08 完成! i=2 i=3 i=4 i=5 i=6

插入排序的基本思想： 有序序列R[1..i-1] 无序序列 R[i..n] R[i] 有序序列R[1..i] 无序序列 R[i+1..n]

插入排序的基本步骤： 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]的位置上。

j 直接插入排序 从R[i-1]向前进行顺序查找，监视哨设置在R[0] R[i] i-1 插入位置 关键字大于R[i].key的记录向后移动 if( L.r[i].key<L.r[i-1].key){ R[0] = R[i]; // 设置“哨兵” R[i] = R[i-1]; for (j=i-2; R[0].key<R[j].key; --j) R[j+1] = R[j]; 循环结束表明R[i]的插入位置为 j+1 L.r[j+1]=L.r[0]; //插入到正确位置

直接插入排序 void InsertSort(SqList ＆L) {int i,j; for(i=2;i<=L.length;++i) if( L.r[i].key<L.r[i-1].key)//将L.r[i]插入有序子表 { L.r[0]=L.r[i]; // 复制为哨兵 L.r[i]=L.r[i-1]; for(j=i-2; L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j]; // 记录后移 L.r[j+1]=L.r[0]; //插入到正确位置 }

算法分析 设对象个数为n，则执行n-1趟 比较次数和移动次数与初始排列有关 for(i=2;i<=L.length;++i) 最好情况下： 　每趟只需比较 1 次，不移动 　总比较次数为 n-1 21 25 49 25* 16 08 for(i=2;i<=L.length;++i) if( L.r[i].key<L.r[i-1].key)

算法分析 比较次数 移动次数 最坏情况下：第 i 趟比较i次，移动i+1次 2018年11月17日2018年11月17日 49 25* 25 21 25 49 25* 16 08 最坏情况下：第 i 趟比较i次，移动i+1次 比较次数 移动次数 if( L.r[i].key<L.r[i-1].key) { L.r[0]=L.r[i]; // 复制为哨兵 L.r[i]=L.r[i-1]; …… L.r[j+1]=L.r[0]; //插入到正确位置 } 2018年11月17日2018年11月17日

算法分析 若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况 平均情况比较次数和移动次数为n2/4 时间复杂度为 o(n2) 是一种稳定的排序方法 21 25 49 25* 16 08 0 1 2 3 4 5 21 25 49 25* 16 08

直接插入排序 减少关键字间的比较次数 折半插入排序 在插入 r[i] 时，利用折半查找法寻找 r[i] 的插入位置

折半插入排序 i=2

折半插入排序 i=3

折半插入排序 i=4

折半插入排序 i=5

折半插入排序 i=6

void BInsertSort ( SqList &L ) { for ( i = 2; i <= L.length ; ++i ) { L.r[0] = L.r[i]; 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; } for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j]; L.r[high+1] = L.r[0]; } // BInsertSort

算法分析 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置

算法分析 当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

算法分析 减少了比较次数，但没有减少移动次数 平均性能优于直接插入排序 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法

希尔排序 算法思想的出发点： 直接插入排序在基本有序时，效率较高 在待排序的记录个数较少时，效率较高 基本思想： 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序 技巧： 子序列的构成不是简单地“逐段分割” 将相隔某个增量dk的记录组成一个子序列 让增量dk逐趟缩短（例如依次取5,3,1） 优点： 小元素跳跃式前移 最后一趟增量为1时，序列已基本有序 平均性能优于直接插入排序

dk 值较大，子序列中对象较少，速度较快； dk 值逐渐变小，子序列中对象变多，但大多数对象已基本有序，所以排序速度仍然很快。 例：关键字序列 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) 49 13 27 38 49* 65 55 97 04 76 13 49 38 27 65 49* 97 55 76 04 第2趟 (dk=3) 13 13 27 04 49* 49* 38 55 27 04 49 49 38 55 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 值逐渐变小，子序列中对象变多，但大多数对象已基本有序，所以排序速度仍然很快。

void ShellSort(SqList &L，int dlta[ ]，int t){ 希尔排序算法（主程序） dk值依次装在dlta[t]中 void ShellSort(SqList &L，int dlta[ ]，int t){ //按增量序列dlta[0…t-1]对顺序表L作Shell排序 for(k=0；k<t；++k) 　ShellInsert(L，dlta[k])； 　 　//增量为dlta[k]的一趟插入排序 } // ShellSort

希尔排序算法（其中某一趟的排序操作） void ShellInsert(SqList &L，int dk) { for(i=dk+1；i<=L.length； ++ i) if(r[i].key < r[i-dk].key) { r[0]=r[i]； for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk) r[j+dk]=r[j]； r[j+dk]=r[0]； } //对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子 //开始将r[i] 插入有序增量子表 //暂存在r[0] //关键字较大的记录在子表中后移 //在本趟结束时将r[i]插入到正确位置

算法分析 时间复杂度是n和d的函数： 空间复杂度为 o(1) O(n1.25）～O（1.6n1.25）—经验公式 是一种不稳定的排序方法 最后一个增量值必须为1，无除1以外的公因子 不宜在链式存储结构上实现

8.3 交换排序 基本思想： 两两比较，如果发生逆序则交换，直到所有记录都排好序为止。 起泡排序O(n2) 快速排序O( nlog2n )

基本思想：每趟不断将记录两两比较，并按“前小后大” 规则交换 起泡排序 基本思想：每趟不断将记录两两比较，并按“前小后大” 规则交换 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

起泡排序 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素； 一旦下趟没有交换，还可提前结束排序

void main() { int a[11]; /*a[0]不用，之用a[1]~a[10]*/ int i,j,t; printf("\nInput 10 numbers: \n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); printf("\n"); for(j=1;j<=9;j++) for(i=1;i<=10-j;i++) if(a[i]>a[i+1]) {t=a[i];a[i]=a[i+1];a[i+1]=t;}//交换 for(i=1;i<=10;i++) printf("%d ",a[i]); }

排序后序列为：13 27 30 38 49 65 76 97 38 例 49 38 65 97 76 13 27 30 初始关键字 n=8 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 13 27 30 38 第五趟 13 27 30 第六趟 13 27 第七趟 49 13 27 38 13 49 27 30 38 76 13 27 65 49 30 38 97 13 76 27 30 49 65 97 27 76 30 65 97 30 76 97

void bubble_sort(SqList &L) { int m,i,j,flag=1; RedType x; m=n-1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L.r[j].key>L.r[j+1].key) { flag=1; x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交换 }//endif m--; }//endwhile } 北京林业大学信息学院

算法分析 设对象个数为n 比较次数和移动次数与初始排列有关 最好情况下： while((m>0)&&(flag==1)) 21 25 49 25* 16 08 算法分析 设对象个数为n 比较次数和移动次数与初始排列有关 最好情况下： 只需 1趟排序，比较次数为 n-1，不移动 while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L.r[j].key>L.r[j+1].key) { flag=1; x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; } ……

算法分析 最坏情况下： 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法 49 25* 25 21 16 08 需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法

快速排序 基本思想： 任取一个元素 (如第一个) 为中心 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表； 对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个

快速排序 pivotkey 49 25 25* 21 16 08 0 1 2 3 4 5 pivotkey 49 25* 25 21 16 0 1 2 3 4 5 pivotkey 49 25* 25 21 16 08 pivotkey 49 25* 25 21 16 08 pivotkey 49 25* 25 21 16 08

49 25 25* 21 16 08

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 65 97 76 13 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 65 97 76 13 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 65 97 76 13 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 97 76 13 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 97 76 13 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 13 97 76 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 13 97 76 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 13 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 13 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 49 27 38 13 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 49 27 38 13 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 27 38 13 49 76 97 65 49 27 38 13 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 27 38 13 49 76 97 65 49 27 13 38 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 27 38 13 49 76 97 65 49 27 13 38 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 27 38 13 49 76 97 65 49 27 13 38 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 27 38 13 49 76 97 65 49 13 27 38 49 76 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 97 65 49 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 97 65 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 97 65 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 65 97 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 65 97 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 65 97 low high 界点

0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 76 13 27 38 49 49 65 97 low high 界点

0 1 2 3 4 5 6 7 8 13 27 38 49 76 97 65 49 13 27 38 49 49 65 76 97 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 49 65 76 97 49 13 27 38 49 65 76 97 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 49 65 76 97 49 13 27 38 49 65 76 97 low high 界点

快速排序 0 1 2 3 4 5 6 7 8 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 low high 界点

快速排序 ①每一趟的子表的形成是采用从两头向中间交替式逼近法； ②由于每趟中对各子表的操作都相似，可采用递归算法。 2018年11月17日2018年11月17日

void main ( ) { QSort ( L, 1, L.length ); } void QSort ( SqList &L，int low, int high ) { if ( low < high ) { pivotloc = Partition(L, low, high ) ; Qsort (L, low, pivotloc-1) ; Qsort (L, pivotloc+1, high ) }

int Partition ( SqList &L，int low, int high ) { L.r[0] = L.r[low]; pivotkey = L.r[low].key; while ( low < high ) { while ( low < high && L.r[high].key >= pivotkey ) --high; L.r[low] = L.r[high]; while ( low < high && L.r[low].key <= pivotkey ) ++low; L.r[high] = L.r[low]; } L.r[low]=L.r[0]; return low;

算法分析 可以证明，平均计算时间是O(nlog2n)。 实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。 快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。 最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n) 。

算法分析 最好：划分后，左侧右侧子序列的长度相同 最坏：从小到大排好序，递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置

算法分析 时间效率：O(nlog2n) —每趟确定的元素呈指数增加 空间效率：O（log2n）—递归要用到栈空间 稳 定 性： 不稳定 —可选任一元素为支点。

8.4 选择排序 基本思想： 每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录

简单选择排序 i =1 i = 2 i = 3 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 25* i =1 25 16 49 08 最小者 08 交换21,08 25 16 08 25* 49 21 i = 2 最小者 16 交换25,16 49 i = 3 08 16 25* 25 21 最小者 21 交换49,21

简单选择排序 i =4 i =5 最小者 25* 无交换 最小者 25 无交换 结果 各趟排序后的结果 49 25* 0 1 2 3 4 5 0 1 2 3 4 5 i =4 08 16 25 21 最小者 25* 无交换 25* i =5 49 最小者 25 无交换 25 21 16 08 25 16 08 25* 49 21 结果 各趟排序后的结果

简单选择排序 void SelectSort(SqList &K) { for (i=1; i<L.length; ++i) { //在L.r[i..L.length] 中选择key最小的记录 k=i; for( j=i+1;j<=L.length ; j++) if ( L.r[j].key <L.r[k].key) k=j; if(k!=i)L.r[i]←→L.r[k]; }

算法分析 移动次数 时间复杂度：O(n²) 空间复杂度：O(1) 稳定 最好情况：0 最坏情况：3(n-1) 比较次数：

树形选择排序 BAO DIAO CHA WANG ZHAO LIU YANG XUE

树形选择排序 DIAO CHA WANG ZHAO LIU YANG XUE

树形选择排序 CHA DIAO LIU WANG ZHAO * YANG XUE

树形选择排序 DIAO LIU WANG ZHAO * YANG XUE

树形选择排序 DIAO LIU ZHAO WANG * YANG XUE

树形选择排序 改进：简单选择排序没有利用上次选择的结果，是造成速度慢的重要原因。如果，能够加以改进，将会提高排序的速度。 13 38 13 选出最小者 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49

树形选择排序 改进：简单选择排序没有利用上次选择的结果，是造成速度满的重要原因。如果，能够加以改进，将会提高排序的速度。 13 38 13 选出次最小者，应利用上次比 较的结果。从被 13 打败的结 点 27、76、38 中加以确定。 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49

什么是堆？ 堆排序 n个元素的序列{k1,k2,…,kn}，当且仅当满足下列关系时，成为堆： 如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。

利用树的结构特征来描述堆，所以树只是作为堆的描述工具，堆实际是存放在线形空间中的。 (09,17,65,23,45,78,87,53,31) (87,78,53,45,65,09,31,17,23) 堆顶元素（根）为最小值或最大值

8 16 9 1 6 2 11 10 5 4 1 6 8 12 9 16 2 11 5 14 大根堆 小根堆

× 1 9 8 10 6 16 2 11 5 4 16 9 8 10 6 2 11 1 5 4

判定(80,75,40,62,73,35,28,50,38,25,47,15)是否为堆 完全二叉树 80 75 40 62 73 28 35 50 38 25 47 15 大根堆

堆排序 基本思想： 如何建？？ 将无序序列建成一个堆 输出堆顶的最小（大）值 使剩余的n-1个元素又调整成一个堆，则可得到n个元素的次小值 重复执行，得到一个有序序列 如何调整？？

如何将无序序列建成堆 思考：有n 个结点的完全二叉树，最后一个分支结点的标号是多少？ n/2 [ 1 ] [ 2 ] 30 [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 30 1 30 60 8 40 70 12 10 60 2 8 3 70 5 10 7 40 4 12 6 思考：有n 个结点的完全二叉树，最后一个分支结点的标号是多少？ n/2

堆 从第n/2个元素起，至第一个元素止，进行反复筛选 [ 1 ] [ 2 ] 70 [ 3 ] 60 [ 4 ] 12 [ 5 ] 40 [ 6 ] [ 7 ] 70 60 12 40 30 8 10 70 1 60 2 12 3 30 5 10 7 40 4 8 6

无序序列建成堆－1 8 [ 1 ] [ 2 ] 30 [ 3 ] 60 [ 4 ] 8 [ 5 ] 40 [ 6 ] 70 [ 7 ] 12 10 30 1 60 2 8 70 5 10 7 3 40 4 12 6

无序序列建成堆－1 12 [ 1 ] [ 2 ] 30 [ 3 ] 60 [ 4 ] 12 [ 5 ] 40 [ 6 ] 70 [ 7 ] 8 10 30 1 60 2 12 70 5 10 7 3 40 4 8 6

无序序列建成堆－2 60 70 [ 1 ] [ 2 ] 30 [ 3 ] 60 [ 4 ] 12 [ 5 ] 40 [ 6 ] 70 [ 7 ] 30 60 12 40 70 8 10 30 1 60 12 10 7 2 3 40 4 70 8 5 6

无序序列建成堆－2 70 60 [ 1 ] [ 2 ] 30 [ 3 ] 70 [ 4 ] 12 [ 5 ] 40 [ 6 ] 60 [ 7 ] 30 70 12 40 60 8 10 30 1 70 12 10 7 2 3 40 4 60 8 5 6

无序序列建成堆－3 30 70 60 [ 1 ] [ 2 ] 30 [ 3 ] 70 [ 4 ] 12 [ 5 ] 40 [ 6 ] 60 [ 7 ] 30 70 12 40 60 8 10 30 1 70 12 10 7 2 3 60 40 4 8 5 6

无序序列建成堆－3 70 30 60 [ 1 ] [ 2 ] 70 [ 3 ] 30 [ 4 ] 12 [ 5 ] 40 [ 6 ] 60 [ 7 ] 70 30 12 40 60 8 10 70 1 30 12 10 7 2 3 60 40 4 8 5 6

无序序列建成堆－3 70 60 30 建堆完毕 [ 1 ] [ 2 ] 70 [ 3 ] 60 [ 4 ] 12 [ 5 ] 40 [ 6 ] [ 7 ] 建堆完毕 70 60 12 40 30 8 10 70 1 60 12 10 7 2 3 30 40 4 8 5 6

堆的重新调整 如何在输出堆顶元素后调整，使之成为新堆？ 筛选 输出堆顶元素后，以堆中最后一个元素替代之 将根结点与左、右子树根结点比较，并与小者交换 重复直至叶子结点，得到新的堆

堆的重新调整－1 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 70 60 12 40 30 8 10 70 1 60 12 10 7 2 3 30 40 4 8 5 6

堆的重新调整－1 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 10 60 10 70 60 12 40 30 8 10 10 40 10 1 60 12 × 2 3 30 40 4 8 70 10 7 5 6 70

× 堆的重新调整－2 40 30 [ 1 ] [ 2 ] 60 [ 3 ] 40 [ 4 ] 12 60 [ 5 ] 10 [ 6 ] 30 [ 7 ] 60 40 12 10 30 8 60 1 40 12 × 2 3 30 10 4 8 70 10 7 5 6 70

堆的重新调整－2 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 40 12 10 30 60 8 1 40 12 2 3 30 10 4 60 60 70 10 7 60 5 6 70

堆的重新调整－2 30 [ 1 ] [ 2 ] 40 [ 3 ] 30 [ 4 ] 12 40 [ 5 ] 10 [ 6 ] 8 [ 7 ] 60 40 1 30 12 2 3 10 4 8 60 60 70 10 7 60 5 6 70

堆的重新调整－3 30 [ 1 ] [ 2 ] 40 [ 3 ] 30 [ 4 ] 12 40 [ 5 ] 10 [ 6 ] 8 [ 7 ] 60 40 1 30 12 2 3 10 4 8 60 60 70 10 7 60 5 6 70

堆的重新调整－3 30 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 30 12 10 60 8 40 10 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－3 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 30 10 12 8 60 30 40 8 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－4 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 30 10 12 8 60 30 40 8 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－4 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 10 12 30 60 8 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－5 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 12 10 8 30 60 12 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－5 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 10 30 60 8 12 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－5 10 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 10 30 60 8 12 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－5 8 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 10 8 30 60 10 12 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－6 8 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 10 8 30 60 10 12 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

堆的重新调整－6 8 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 8 30 60 10 10 8 12 1 8 30 10 12 8 2 3 40 30 30 4 40 8 60 60 70 10 7 60 5 6 70

算法分析 时间效率：O(nlog2n) 空间效率：O（1） 稳 定 性：不稳定 适用于n 较大的情况

8.5 归并排序 归并：将两个或两个以上的有序表组合成一个新有序表 2-路归并排序 排序过程 初始序列看成n个有序子序列，每个子序列长度为1

将两个顺序表合并成一个有序表 i A 13 49 65 97 j B 7 76 80 k C 0 1 2 3 4 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49 65

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49 65

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 7 13 C 49 65 76

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 7 13 49 65 C 76

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49 65 76 80

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 C 7 13 49 65 76 80

B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可 i 0 1 2 3 4 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 7 13 49 65 C 76 80

i 0 1 2 3 4 A 13 49 65 97 j B 7 76 80 k 0 1 2 3 4 5 6 7 7 13 49 65 C 76 80 97

例 初始关键字： [49] [38] [65] [97] [76] [13] [27] 一趟归并后： [38 49] [65 97] [13 76] [27] 二趟归并后： [38 49 65 97] [13 27 76] 三趟归并后： [13 27 38 49 65 76 97]

算法分析 时间效率：O(nlog2n) 空间效率：O（n） 稳 定 性：稳定

以扑克牌排序为例。每张扑克牌有两个“排序码”：花色和面值。其有序关系为： 花色：       面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 可以把所有扑克牌排成以下次序：  2, …,  A,  2, …,  A,  2, …,  A,  2, …,  A 花色相同的情况下，比较面值。

8.6 基数排序 前面的排序方法主要通过关键字值之间的比较和移动 而基数排序不需要关键字之间的比较 对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（ <<< ） 面值（2<3<……<A） 并且“花色”地位高于“面值”

多关键字排序 链式基数排序 最高位优先MSD ( Most Significant Digit first ) 最低位优先LSD ( Least Significant Digit first) 链式基数排序 链式基数排序：用链表作存储结构的基数排序

最高位优先法 先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值； 然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列； 依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。 十进制数比较可以看作是一个多关键字排序

最高位优先法 十位

最低位优先法 首先依据最低位排序码Kd对所有对象进行一趟排序 再依据次低位排序码Kd-1对上一趟排序结果排序 依次重复，直到依据排序码K1最后一趟排序完成，就可以得到一个有序的序列。 这种方法不需要再分组，而是整个对象组都参加排序

最低位优先法

利用“分配”和“收集”对关键字进行排序 链式基数排序 先决条件： 过程 知道各级关键字的主次关系 知道各级关键字的取值范围 首先对低位关键字排序，各个记录按照此位关键字的值‘分配’到相应的序列里。 按照序列对应的值的大小，从各个序列中将记录‘收集’，收集后的序列按照此位关键字有序。 在此基础上，对前一位关键字进行排序。

初始状态： 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 083 184 505 008 269 589 063 278 109 930 063 083 184 505 278 008 109 589 269 一趟收集：

930 063 083 184 505 278 008 109 589 269 一趟收集 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 109 930 269 589 278 008 184 505 063 083 505 008 109 930 063 269 278 083 184 589 二趟收集：

505 008 109 930 063 269 278 083 184 589 二趟收集 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 083 184 278 589 930 063 008 109 269 505 008 063 083 109 184 269 278 505 589 930 三趟收集：

链式基数排序步骤 设置10个队列，f[i]和e[i]分别头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列

算法分析 n个记录 每个记录有 d 位关键字 关键字取值范围rd(如十进制为10) 时间效率：O(d( n+rd)) 空间效率：O(n+rd) 稳 定 性：稳定

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

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

外部排序的基本方法 假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。 分析上述外排过程中访问外存(对外存进行读/写)的次数： 假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。 则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。 1)求得10个初始归并段需访问外存100次; 2)每进行一趟归并需访问外存100次; 3)总计访问外存 100 + 4  100 = 500次

外部排序的基本方法 外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间 外部排序总时间=产生初始归并段的时间 m*tIS +外存信息读写时间 d*tIO +内部归并所需时间 s*utmg tIO值取决于外存，远远大于tIS和tmg。 外部排序的时间取决于读写外存的次数d。

外部排序的基本方法 例如:若对上述例子采用2路归并,则只需进行4趟归并， 外排所需总的时间： 10*tIS+500*tIO+4*1000*tmg 若对上述例子采用5路归并,则只需进行2趟归并，总的访问外存的次数为100+2100=300次 一般情况下，假设待排记录序列含 m 个初始归并段，外排时采用 k路归并，则归并趟数s=logkm，显然，随着k的增大或m的减小，归并的趟数将减少，因此对外排而言，通常采用多路归并。k 的大小可选，但需综合考虑各种因素。

多路平衡归并的实现 一、多路平衡归并的性质： 分析: m 个初始归并段，外排时采用 k路归并，则归并趟数为 logkm , K 大，趟数减少，读写记录的总数将减少。但 K 大，会使内部归并时间tmg增大?。

多路平衡归并的实现 设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为 tmg，在进行 k 路平衡归并时,要得到m个初始归并段,则内部归并过程中进行的比较的总的次数为: logkm × ( k - 1 ) × ( n - 1 ) × tmg = log2m ×( k - 1 ) / log2k × ( n - 1 ) × tmg 改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需 log2k 次比较，这时总的时间耗费将下降为： log2m × ( n - 1 ) × tmg

多路平衡归并的实现 二、胜者树及其使用 4路平衡归并 1 7 6 5 4 3 2 1 9 29 5 2 3 5 9 4 5 6 7 5 7 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5

多路平衡归并的实现 二、胜者树及其使用 4路平衡归并 1 1 2 3 4 5 6 7 7 7 7 9 16 7 29 9 2 3 7 9 4 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5 7

多路平衡归并的实现 二、胜者树及其使用 4路平衡归并 1 1 2 3 4 5 6 7 9 9 12 9 16 12 29 9 2 3 12 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5 7 9

多路平衡归并的实现 采用胜者树，从 K 个元素中挑选一个最小的元素仅需 log2m × ( n - 1 ) × tmg 即内部归并时间与k无关, K 增大，归并趟数logkm减少，读写外存次数减少，外排总时间减少。 改进：采用胜者树，从K个元素中选取最小元素之后，从根结点到它的相应的叶子结点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。

多路平衡归并的实现 4路平衡归并 三、败者树及其使用 ls [0] ls[1] 1 2 3 4 5 6 7 3 5 9 7 29 5 7 ls[1] 1 2 3 4 5 6 7 3 5 9 7 29 5 7 29 9 ls[2] ls[3] 1 2 b[1] b[2] b[3] b[0] 5 7 29 9 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5

多路平衡归并的实现 4路平衡归并 三、败者树及其使用 ls [0] 1 ls[1] 1 2 3 4 5 6 7 3 5 9 7 29 5 7 1 2 3 4 5 6 7 3 5 9 7 29 5 7 29 9 ls[2] ls[3] 2 b[1] b[2] b[3] b[0] 16 7 29 9 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5 7

多路平衡归并的实现 4路平衡归并 三、败者树及其使用 ls [0] 3 ls[1] 1 2 3 4 5 6 7 1 5 9 7 29 5 7 1 2 3 4 5 6 7 1 5 9 7 29 5 7 29 9 ls[2] ls[3] 2 b[1] b[2] b[3] b[0] 16 12 29 9 注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。 输 入 缓 冲 区 5 16 49 52 78 7 12 25 84 91 29 38 57 66 71 9 22 47 48 59 输 出 缓 冲 区 5 7 9 …

置换-选择排序 一、问题的提出 m个初始归并段做k路平衡归并排序时归并的趟数为logkm.为了减少归并趟数，也可以减小m的值。如何减小初始归并段的个数（也就是增加归并段的长度）? 解决：在内存长度一定时，假设容纳M条记录，按照通常的 排序方法，初始归并段的长度可以是M 一种更好的方法是使用置换选择(replace selection)算法，平均情况下可以产生可以生成两倍内存长度的初始归并段。

置换-选择排序 2.置换选择排序 置换选择排序是堆排序的变体。 内存工作区可容纳w个记录 输出文件Fo 输出缓冲 输入文件FI 输入缓冲 内存工作区WA 内存工作区可容纳w个记录

置换-选择排序的操作过程 (1) 从FI输入W个记录到WA； (2) 从WA中选择关键字最小的记录，记为MINIMAX (3) 将MINIMAX输出到FO中； (4)若FI不空，从FI输入下一个记录到WA； (5)从WA中所有关键字比MINIMAX的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。 (6)重复（3）-（5）直至WA中选不出新的MINIMAX。到此得到一个初始归并段 （7）重复（2）-（6），直至WA为空。

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 51 49 39 46 38 29 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 51 49 39 46 38 14 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 51 49 46 39 14 61 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 51 49 46 14 61 15 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 51 49 14 61 15 30 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 14 61 15 30 1 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 # 14 61 15 30 1 48 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 14 15 30 1 48 52 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61# 14 15 30 1 48 52 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 14 15 30 48 52 3 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 30 48 52 63 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 30 48 52 63 27 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 30 48 52 63 27 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 30 48 52 63 27 4 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 4 13 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 4 13 89 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 4 13 89 24 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 4 13 89 24 46 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 4 13 89 24 46 58 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 46 58 33 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 46 58 33 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 46 58 33 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 46 58 33 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 FI WA FO

实例：输入文件FI中记录关键字为：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 个记录，利用置换-选择分类法产生初始合并段。 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 # FI WA FO

置换-选择排序 3、长度分析： 设内存可以存放 m 个记录，则首先从文件读入 m 记录到内存。这 m 个记录肯定可以归入本初始合并段内。这样，必须从文件中读入 m 个记录。这 m 个记录中平均有一半可以归入本合并段，一半归入下一合并段。 因此，合并段的平均长度为： m + m/2 + m/4 + ………… = 2m 所以，在平均情况下，合并段的平均长度为 2m 。 该结论由：E·F·Moore 在 1961 年从置换－选择排序同扫雪机的类比中得到的。

置换-选择排序的实现 1)存储结构定义 可以用败者树的办法 加以实现。 typedef struct {RcdType rec; //记录 KeyType key; //关键字 int rnum; //所属归并段的段号 }RcdNode,WorkArea[w];

2)模块结构图 Replace_selection Get_run 置换-选择算法 Construct_Loser 得到一个初始归并段 Select_MiniMax 选择每个段中最小值

3)模块实现 void Replace_Selection(LoserTree &ls, WorkArea &wa, FILE *fi,FILE *fo) {Construct_Loser(ls, wa); rc=rmax=1; //rc为当前生成段号，rmax为最大段的段号 while(rc<=rmax) {get_run(ls, wa); fwrite(RUNEND_SYMBLE, sizeof(struct RcdType), 1, fo); rc=wa[ls[0] ].rnum; } }//Replace_Selection

void get_run(LoserTree &ls, WorkArea &wa){ while(wa[ls[0] ].rnum==rc) {q=ls[0]; minimax=wa[q].key; fwrite(&wa[q].rec, sizeof(struct RcdType), 1, fo); If(feof( f i ) {wa[q].rnum=rmax+1; wa[q].key=MAXKEY;} else { fread(&wa[q].rec,sizeof(struct RcdType),1, fi); wa[q].key=wa[q].rec.key; If(wa[q].key<minimax) {rmax=rc+1; wa[q].rnum=rmax;} else wa[q].rnum=rc; } select_MiniMax(ls, wa, q); }//while }//get_run

void Select_MiniMax(LoserTree &ls, WorkArea wa, int q){ for(t=(w+q)/2, p=ls[t]; t>0; t=t/2, p=ls[ t ] ) if(wa[p].rnum<wa[q].rnum || wa[p].rnum==wa[q].rnum && wa[p].key < wa[q].key) qls[t]; ls[0]=q; }

void Construct_Loser(LoserTree &ls, WorkArea &wa) {for(i=0; i<w; ++i) wa[i].rnum=wa[i].key=ls[i]=0; for(i=w-1; i>=0; - -i){ fread(&wa[i].rec, sizeof(struct RcdType), 1, fi); wa[i].key=wa[i].rec.key; wa[i].rnum=1; Select_MiniMax(ls, wa, i); }//end for }//Construct_Loser

败者树实现置换-选择排序 3 51、49、39、46、38、29、14、61、15 4 1 1 2 5 29 1 38 1 2 3 4 5 3 51、49、39、46、38、29、14、61、15 4 1 1 2 5 29 1 38 1 2 3 4 5 46 1 39 1 49 1 51 1 29

1 3 51、49、39、46、38、29、14、61、15 4 1 2 5 14 2 38 1 2 3 4 5 46 1 39 1 49 1 51 1 29 38

3 1 51、49、39、46、38、29、14、61、15 4 1 2 5 14 2 61 1 2 3 4 5 46 1 39 1 49 1 51 1 29 38 39

2 1 51、49、39、46、38、29、14、61、15 4 1 3 5 14 2 61 1 2 3 4 5 46 1 15 2 49 1 51 1 注意：在全部的 段号标志变成 2 之后，合并段 1 的记录已全部生 成。 29 38 39 46 ？K 值越大越好吗！

最佳归并树 起因：由于初始归并段通常不等长,进行归并时,长度不同的初始归并段归并的顺序不同,读写外存的总次数也不同。 目的：减少读写外存的次数。

e.g:假定由置换－选择分类法生成了 9 个初始归并段，记录数分别为 9、30、12、18、3、17、2、6、24 。如果进行 3-路归并，请讨论在各种情况下的对外存的读写次数。 A. 9 30 12 18 3 17 2 6 24 从外存读 121 个记录 51 38 32 写入外存 121 个记录 从外存读 121 个记录 121 写入外存 121 个记录 总共读写外存 484 个记录

B. 2 3 6 从外存读 11 个记录 9 12 17 18 24 写入外存 11 个记录 11 从外存读 91个记录 30 32 59 写入外存 91 个记录 从外存读 121 个记录 写入外存 121 个记录 121 总共读写外存 446 个记录

按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。如下例所示。 C. 从外存读 5个记录 2 3 12 17 18 写入外存 11 个记录 6 9 5 20 写入外存 67 个记录 47 24 从外存读 91个记录 91 写入外存 91 个记录 总共读写外存 326 个记录

虚段的补法: 在 K 路平衡归并时，它的归并树的模型是一棵度为 K 的树。在这棵树上的结点要么是叶子，要么是具有 K 个子女的内部结点。设具有 K 个子女的内部结点共有 nk 个。初始归并段的个数为 m 个。设 n = nk + m ，故：从结点出发的枝条，共计有K × nk 个。若从进入结点的角度进行考虑，则共有： nk + m － 1 注意：没有枝条进入根结点。 所以， K × nk ＝ nk + m － 1 于是： nk ＝ ( m － 1 ) / ( K - 1) 这就意味着，若 ( m － 1 ) MOD ( K - 1) ＝ 0，无需增加虚段。否则，要增加虚段，其数目为： （ K－1）－ ( m － 1 ) MOD ( K - 1)

限制： 由于磁带寻找具有最少记录的初始归并段，必须反复倒带。所以，实用性不强。 在磁盘的情况下，需要有段包含的记录数信息、段的位置信息等。文件如集中放置在几个相邻的柱面上的情况比较合适。

小结 1. 熟练掌握直接插入排序、折半插入排序、冒泡排序、快速排序、直接选择排序的算法实现及其性能分析 2. 掌握希尔排序、归并排序、堆排序的方法及其性能分析 3.各种内部排序方法的比较（时间、空间、稳定性、选择原则） 4.堆的概念、判别方法、存储结构 5. 掌握外部排序方法中败者树的建立及归并方法，掌握置换-选择排序的过程和最佳归并树的构造方法

排序算法比较 （数据不是顺次后移时将导致方法不稳定） 北京林业大学信息学院

排序算法比较 按平均时间排序方法分为四类 O(n2)、O(nlogn)、O(n1+)、O(n) 快速排序是基于比较的内部排序中平均性能最好的 基数排序时间复杂度最低，但对关键字结构有要求 知道各级关键字的主次关系 知道各级关键字的取值范围

排序算法比较 为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构 直接插入排序、归并排序、基数排序 不宜采用链表作为存储结构的 　　　直接插入排序、归并排序、基数排序 不宜采用链表作为存储结构的 　　　折半插入排序、希尔排序、快速排序、堆排序

排序算法选择规则 n较大时 n较小时 （1）分布随机，稳定性不做要求，则采用快速排序 （2）内存允许，要求排序稳定时，则采用归并排序 （3）可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序 n较小时 （1）基本有序，则采用直接插入排序 （2）分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序