北京大学：《数据结构与算法》课程教学资源（实验班讲义）第七章 内排序

数据结构与算法 大纲 71基本概念 第七章内排序 ■72三种O(m2)的简单排序 73She排序 任课教员:张铭 ■74基于分治法的排序 http://db.pku.edu.cn/mzhang/ds/ 75堆排序 mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 76分配排序和基数排序 网络与信息系统研究 77排序算法的理论和实验时间代价 ⊙版权所有,转载或翻印必究 28排序回题的下限 排序问题 小规模的排序问题 ■ Google等搜索引擎返回结果排级 图书馆员书目编号、上架 个元素 各种排名 已经有序了 考试成绩排名 两个元素 福布斯》富豪榜 次比较 Windows资源管理器,文件查看 若逆序? 次交换=3次移动(赋值) n个元素? 北大影_歌张写 权质有轨国邮究 张铭编写 有,神剑究 排序算法的分类1 排序算法的分类2 插入排 自底向上求解 交换排序、She排序 三种o(m2)的简单排序 插入排序、冒泡排序、选择排序 She排序 ■选择排序 堆排序 直接选择排序、堆排序 归并排序 自顶向下求解:基于分治法的排序 ■分配排序 归并排序、快速排序 自底向上:低位优先LsD 分配排序 页向下:高位优先MSD 自底向上:低位优先LsD ■地址排序 自顶向下:高位优先MSD 北大张写 权所有轨康■命邮 _张铭编写 新有,种究

1 数据结构与算法 第七章 内排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 大纲 „ 7.1 基本概念 „ 7.2 三种Ｏ(n2)的简单排序 „ 7.3 Shell排序 „ 7.4 基于分治法的排序 „ 7.5 堆排序 „ 7.6 分配排序和基数排序 „ 7.7 排序算法的理论和实验时间代价 „ 7.8 排序问题的下限 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 排序问题 „ Google等搜索引擎返回结果排级 „ 图书馆员书目编号、上架 „ 各种排名 „ 大学排名 „ 考试成绩排名 „ 《福布斯》 富豪榜 „ Windows资源管理器，文件查看 „ www.kooxoo.com „ …… 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 小规模的排序问题 „ 一个元素 „ 已经有序了 „ 两个元素 „ 一次比较 „ 若逆序？ „ 一次交换 = 3次移动（赋值） „ n个元素？ 45 34 45 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 排序算法的分类1 „ 插入排序 „ 直接插入排序、Shell排序 „ 交换排序 „ 冒泡排序、快速排序 „ 选择排序 „ 直接选择排序、堆排序 „ 归并排序 „ 分配排序 „ 自底向上：低位优先LSD „ 自顶向下：高位优先MSD „ 地址排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 排序算法的分类2 „ 自底向上求解 „ 三种Ｏ(n2)的简单排序 „ 插入排序、冒泡排序、选择排序 „ Shell排序 „ 堆排序 „ 自顶向下求解：基于分治法的排序 „ 归并排序、快速排序 „ 分配排序 „ 自底向上：低位优先LSD „ 自顶向下：高位优先MSD

7.1.1基本概念 什么是排序? 记录( Record):结点,进行排序的基 本单位 排序 关键码Key):唯一确定记录的一个 将序列中的记录按照排序码顺序排列起来 或多个域 排序码域的值具有不减(或不增)的顺序 排序码( Sort Key):作为排序运算依 内排序 的一个或多个 n整个排序过程在内存中完成 序列( equence):线性表 由记录组成 北大▲单张铭搞写 有,郭位詹命究 北大息_张铭写 排序问题 正序vs逆序 给定一个序列R={r1,r2,…,rn} “正序序列:待排序序列正好符合 其排序码分别为k={k1 排序要求 排序的目的:将记录按排序码重排 “逆序序列:把待排序序列逆转过 形成新的有序序列R'={rlpr2 n 来,正好符合排序要求 相应排序码为k={k'1,k2…,k23 ■排序码的顺序 例如,要求不升序列逆序 其中k1≤k2≤…≤kn,称为不减序 n08123496 或k'1≥k2,≥ka,称为不增序 °6341208-正序! 北大影_歌张写 权质有轨国邮究 真大影张帖写 叔新有,量究 排序的稳定性 排序算法的衡量标准 稳定性 时间代价:记录的比较和移动次数 存在多个具有相同排序码的记录 ■空间代价 排序后这些记录的相对次序保持不变 ■例如,341234′0896 0812343496—稳定 算法本身的繁杂程度 081234′3496—不稳定 北真大学张铭编写 聊张帖写 权新有,究

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 7.1.1 基本概念 „ 记录(Record)：结点，进行排序的基 本单位 „ 关键码(Key)：唯一确定记录的一个 或多个域 „ 排序码(Sort Key)：作为排序运算依 据的一个或多个域 „ 序列(Sequence)：线性表 „ 由记录组成 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 什么是排序？ „ 排序 „ 将序列中的记录按照排序码顺序排列起来 „ 排序码域的值具有不减(或不增)的顺序 „ 内排序 „ 整个排序过程在内存中完成 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 排序问题 „ 给定一个序列R ={r1, r2, …，rn} „ 其排序码分别为k ={k1, k2, …，kn} „ 排序的目的：将记录按排序码重排 „ 形成新的有序序列R’= {r’1, r’2, …，r’n} „ 相应排序码为k’ ={k’1, k’2, …，k’n} „ 排序码的顺序 „ 其中k’1≤k’2≤…≤k’n，称为不减序 „ 或k’1≥k’2≥…≥k’n ，称为不增序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 正序 vs. 逆序 „ “正序”序列 ：待排序序列正好符合 排序要求 „ “逆序” 序列 ：把待排序序列逆转过 来，正好符合排序要求 „ 例如，要求不升序列 „ 08 12 34 96 „ 96 34 12 08 逆序！ 正序！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 排序的稳定性 „ 稳定性 „ 存在多个具有相同排序码的记录 „ 排序后这些记录的相对次序保持不变 „ 例如，34 12 34’ 08 96 „ 08 12 34 34’ 96——稳定！ „ 08 12 34’ 34 96——不稳定！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 排序算法的衡量标准 „ 时间代价：记录的比较和移动次数 „ 空间代价 „ 算法本身的繁杂程度

713常用类和函数 总的排序类 emplate ■总的排序类 r【//总排 Compare类 交换数组中的两个元素 static void swap(Record array,int i, int D); p函数 PrintArray函数 //对数组Aray进行排序 void Sort(Record Array[,int n); /输出数组内容 举位▲张倍墙写 tti void PrintArray(Record arrayAl, int n); 张铭写 叔新有,命邮 Compare类 int intcompare类 Compare类是用来比较记录的 class int_ intCompare t /比较两个整型记录大小 排序码 publiC: 模板参数,方便针对不同类型的 static bool lt(int x,int y ireturn xyi] ■为了简便起见,本教材讨论整数 tatic bool le int x, int y ireturn x=yi] 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 swap函数 PrintArray函数 template template void Sorter void Sorter swap(Record array[]int i, int J PrintArray (Record Array, int n) //交换数组中的两个元素 //输出数组内容 ecord TempRecord Array[i] for(int i=O;i<n;i++) Array[i] array]; cout <<Array[i]<<i Array[] TempRecord cout<<endl 北真大学张铭编写 聊张帖写 权新有,究

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 7.1.3 常用类和函数 „ 总的排序类 „ Compare类 „ Swap函数 „ PrintArray函数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 总的排序类 template class Sorter{ //总排序类 protected: //交换数组中的两个元素 static void swap(Record Array[],int i,int j); public: //对数组Array进行排序 void Sort(Record Array[],int n); //输出数组内容 void PrintArray(Record array[], int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 Compare类 „ Compare类是用来比较记录的 排序码 „ 模板参数，方便针对不同类型的 排序码进行比较 „ 为了简便起见，本教材讨论整数 排序的例子 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 int_intCompare 类 class int_intCompare { //比较两个整型记录大小 public: static bool lt(int x,int y) {return xy;} static bool le(int x,int y) {return x=y;} }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 swap函数 template void Sorter:: swap(Record Array[],int i,int j) { //交换数组中的两个元素 Record TempRecord = Array[i]; Array[i] = Array[j]; Array[j] = TempRecord; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 PrintArray函数 template void Sorter:: PrintArray(Record Array[], int n) { //输出数组内容 for(int i=0;i<n;i++) cout<<Array[i]<<" "; cout<<endl; }

士 72三种O(m2)的简单排序 7.21插入排序 插入排序( Insert Sort) 算法思想 ■冒泡排序( Bubble sort) 算法演示 选择排序( Selection sort) ■直接插入排序 ■优化的插入排序 带监视哨的插入排序 ■二分法插入排序 举位▲张倍墙写 北大单张铭写 叔新有,命邮 45‖ template =134.4578123432296 wpid StraightInsertSorter 4 ‖1234322964 /Aray[]为待排序数组,n为数组长度 i=312344578|332296 for(inti=1;iO;j--)t i=412342.4578‖322964 if (Compare: : lt(Array D], Array[-1]) =5123234344578‖2964 else break;//此时前面记录已排序 i=7122932343445478‖ 大张帖写 叔新有,量究 算法分析 优化的插入排序算法 稳定 uplate 时间代价: class ImprovedInsertsorter: public 最佳情况:n-1次比较,0次交换,e(n) Insertsorter 最差情况:比较和交换次数为 //优化的插入排序类 ∑i=n(n-1)/2=6(2) void Sort(Record Array lint n; 平均情况:e(n2) 北真大学张铭编写 聊张帖写 权新有,究

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 7.2 三种Ｏ(n2)的简单排序 „ 插入排序(Insert Sort) „ 冒泡排序(Bubble Sort) „ 选择排序(Selection Sort) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 7.2.1 插入排序 „ 算法思想 „ 算法演示 „ 直接插入排序 „ 优化的插入排序 „ 带监视哨的插入排序 „ 二分法插入排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 45‖ 34 78 12 3 4 32 29 64 i=1 34 45‖ 78 12 3 4 32 29 64 i=2 34 45 78‖ 12 3 4 32 29 64 i=3 12 34 45 78‖ 3 4 32 29 64 i=4 12 34 3 4 45 78‖ 32 29 64 i=5 12 32 34 3 4 45 78‖ 29 64 i=6 12 29 32 34 3 4 45 78‖ 64 i=7 12 29 32 34 3 4 45 64 78‖ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 template void StraightInsertSorter:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 for (int i=1; i0;j--) { if (Compare::lt(Array[j], Array[j-1])) swap(Array, j, j-1); else break; //此时i前面记录已排序 } } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 算法分析 „ 稳定 „ 空间代价：Θ(1) „ 时间代价： „ 最佳情况：n-1次比较，0次交换，Θ(n) „ 最差情况：比较和交换次数为 „ 平均情况：Θ(n2) 1 2 1 ( 1) / 2 ( ) n i i nn n − = ∑ = − =Θ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 优化的插入排序算法 template class ImprovedInsertSorter:public InsertSorter { //优化的插入排序类 public: void Sort(Record Array[],int n); };

template void ImprovedInsertsorter Sort(Record Arrayal, int n) ∥/Aray[]为待排序数组,n为数组长度 二分法插入排序 Record TempRecord临时变量 for(inti=1i 4 class BubbleSorter: public 2932a445348 Sorter //冒泡排序类 i=51229323434456478 void Sort(Record Array [ int n); i=6 1229323434456478 71229323434456478 聊张帖写 权新有,究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 template void ImprovedInsertSorter:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量 for (int i=1; i=0) && (Compare::lt(TempRecord, Array[j]))) { Array[j+1] = Array[j]; j = j - 1; } //此时j后面就是记录i的正确位置，回填 Array[j+1] = TempRecord; } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 二分法插入排序 „ 算法思想： „ 在插入第i个记录时，前面的记录 已经是有序的了 „ 可以用二分法查找第i个记录的正 确位置 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 算法分析 „ 稳定 „ 空间代价：Θ(1) „ 时间代价： „ 插入每个记录需要Θ(log i)次比较 „ 最多移动i+1次 ，最少2次（移动临时记 录） „ 因此最佳情况下总时间代价为 Θ(nlog n) ，最差和平均情况下仍为Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 7.2.2 冒泡排序 „ 算法思想： „ 不停地比较相邻的记录，如果不 满足排序要求，就交换相邻记 录，直到所有的记录都已经排好 序。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 45 34 78 12 3 4 32 29 64 i=1 12 45 34 78 29 3 4 32 64 i=2 12 29 45 34 78 32 3 4 64 i=3 12 29 32 45 34 78 3 4 64 i=4 12 29 32 34 45 3 4 78 64 i=5 12 29 32 34 3 4 45 64 78 i=6 12 29 32 34 3 4 45 64 78 i=7 12 29 32 34 3 4 45 64 78 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 冒泡排序类 template class BubbleSorter:public Sorter { //冒泡排序类 public: void Sort(Record Array[],int n); };

冒泡排序算法 算法分析 template void Bubble Sorter:: 稳定 Sort( Record array[, int n) //冒泡排序,Aray[]为待排数组,n为数组长度 空间代价:e(1) /第个记录冒泡 ■时间代价 for(int i=l; i=i; j-) 交换次数最多为e(n2),最少为0,平均 if (Compare: lt(Array l, Array l-1]) 为e(n2)。 swap(Array, j, j-1); 最大,最小,平均时间代价均为e(n2)。 } 举位▲张倍墙写 北大单张铭写 叔新有,命邮 优化的冒泡排序 优化的冒泡排序 改进:检查每次冒泡过程中是否 emplate 整个数组已经排好序了,排序结 class Improved BubbleSorter: public Sorter 束 //优化的冒泡排序类 避免不必要的比较 public: void Sort (Record array lint n) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 template void Improved Bubble Sorter Sort( Record Array[, int n) bool NoSwap;//是否发生交换的标志 算法分析 for(int i=1; i<n; i++)t NoSwap=true;∥/标志初始为真 ■稳定 Compare::lt(Arrayal, Array[j-1]) //如果发生了交换,标志变为假 空间代价为⊙(1) swap(Array, j, j-1); NoSwap false ■时间代价: 最小时间代价为e(n):最佳情况 /没发生过交换,已排好序,结束算法 A(NoSwap)return 下只运行第一轮循环 a其他情况下时间代价仍为e(n2) 北真大学张铭编写 聊张帖写 权新有,究 6

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 冒泡排序算法 template void BubbleSorter:: Sort(Record Array[], int n) { //冒泡排序，Array[]为待排数组，n为数组长度 //第i个记录冒泡 for (int i=1; i=i; j--) if (Compare::lt(Array[j], Array[j-1])) swap(Array, j, j-1); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 算法分析 „ 稳定 „ 空间代价：Θ(1) „ 时间代价 ： „ 比较次数 ： „ 交换次数最多为Θ(n2)，最少为0，平均 为Θ(n2)。 „ 最大，最小，平均时间代价均为Θ(n2)。 1 2 1 ( ) ( 1) / 2 ( ) n i n i nn n − = ∑ − = − =Θ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 优化的冒泡排序 „ 改进：检查每次冒泡过程中是否 发生过交换，如果没有，则表明 整个数组已经排好序了，排序结 束。 „ 避免不必要的比较 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 优化的冒泡排序 template class ImprovedBubbleSorter:public Sorter { //优化的冒泡排序类 public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 template void ImprovedBubbleSorter:: Sort(Record Array[], int n) { bool NoSwap; // 是否发生交换的标志 for (int i=1; i=i; j--) if (Compare::lt(Array[j], Array[j-1])) {//如果发生了交换，标志变为假 swap(Array, j, j-1); NoSwap = false; } // 没发生过交换，已排好序，结束算法 if (NoSwap) return; } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 算法分析 „ 稳定 „ 空间代价为Θ(1) „ 时间代价： „ 最小时间代价为Θ(n)：最佳情况 下只运行第一轮循环 „ 其他情况下时间代价仍为Θ(n2)

3478 34322964 7.23直接选择排序 78453432296 ■算法思想 =11229 4534323464 找出剩下的未排序记录中的最小 12293 464 记录,然后直接与数组中第个记 录交换,比冒泡排序减少了移动 1=312293234g74564 次数 1229323437564 1229323434586 举位▲张倍墙写 229323434 template : 直接选择排序 Sort(Record Array ll, int n) 依次选出第小的记录,即剩余记录中最小的那个 template class Straightselectsorter:public /开始向后扫描所有剩余记录 Sorter ∥/如果发现更小的记录,记录它的位置 /直接选择排序类 public void Sort(Record Array[],int n); 将第小的记录放在数组中第个位置 swap(Array, i, Smallest) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 724简单排序算法的时间代 算法分析 价对比 ■不稳定 比较次数立接插改进二分法插冒泡排改进的选择 入排序序冒泡排排序 空间代价:⊙(1) 时间代价 最佳情况e(n)e(n)e( nlog n)e(n)e(n)e(n2) a比较次数:e(n2),与冒泡排序一样 交换次数:n-1 平均情况e(n)e(m)e( nlog n)e(m)e(m3)e(m2 总时间代价:e(n2) 最差情况e(n)e(m)e( nlog n)e(m)e(m)e(m2 北真大学张铭编写 聊张帖写 权新有,究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 7.2.3 直接选择排序 „ 算法思想: „ 找出剩下的未排序记录中的最小 记录，然后直接与数组中第i个记 录交换 ，比冒泡排序减少了移动 次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 45 34 78 12 3 4 32 29 64 i=0 12 34 78 45 3 4 32 29 64 i=1 12 29 78 45 3 4 32 34 64 i=2 12 29 32 45 3 4 78 34 64 i=3 12 29 32 34 3 4 78 45 64 i=4 12 29 32 34 3 4 78 45 64 i=5 12 29 32 34 3 4 45 78 64 i=6 12 29 32 34 3 4 45 64 78 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 直接选择排序 template class StraightSelectSorter:public Sorter { //直接选择排序类 public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 template Void StraightSelectSorter:: Sort(Record Array[], int n) { // 依次选出第i小的记录，即剩余记录中最小的那个 for (int i=0; i<n-1; i++) { // 首先假设记录i就是最小的 int Smallest = i; // 开始向后扫描所有剩余记录 for (int j=i+1;j<n; j++) // 如果发现更小的记录，记录它的位置 if (Compare::lt(Array[j], Array[Smallest])) Smallest = j; //将第i小的记录放在数组中第i个位置 swap(Array, i, Smallest); } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 算法分析 „ 不稳定 „ 空间代价：Θ(1) „ 时间代价 ： „ 比较次数：Θ(n2)，与冒泡排序一样 „ 交换次数：n-1 „ 总时间代价：Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 7.2.4 简单排序算法的时间代 价对比 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n Θ(nlog n) ) 2 Θ(n ) 2 最差情况 ) Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n Θ(nlog n) ) 2 Θ(n ) 2 平均情况 ) Θ(n2 Θ(n Θ(n) ) 2 最佳情况 Θ(n) Θ(n) Θ(nlog n) ) 选择 排序 改进的 冒泡排 序 冒泡排 序 二分法插 入排序 改进 的插 入排 序 直接插 入排序 比较次数

移动次直接改进的二分冒泡改进选择 总代价直接改进的二分法冒泡改进的选择 插入插入排法插排序的冒排序 插入插入排插入排排序冒泡排排序 排序序 泡排 排序序 最佳情e(m)e(n) e(nlog叫me(n2e(mn)e(m 最佳情 e(n)e(n)0 e(n) 均情e(n2)e(m2)e(m3)e(m2e(m3)e( 平均情emne(m)e(n)e(n)e(n)e(m) 最差情e(m2)6(n2)e(m2)e(m2e(mn)e(m 最差情e(m)e(n2)e(m2)e(m2)emn)e(n) A上 聊脑张写 叔新有,命邮 原因 7.3Shel1排序 ■一个长度为n序列平均有n(n-1)/4 ■直接插入排序的两个性质: 对逆置 在最好情况(序列本身已是有序 任何一种只对相邻记录进行比较 的)下时间代价为e(n) 的排序算法的平均时间代价都是 对于短序列,直接插入排序比较 有效 e(n2) She排序有效地利用了直接插 入排序的这两个性质 北真大脆张写 版叔斯有就即究 叔新有,量究 Shel1排序 算法思想 先将序列转化为若干小序列,在这些 序列内进行插入排序 221125a78,62 ■逐渐扩大小序列的规模,而减少 列个数,使得待排序序列逐渐处 有序的状态 d122123453178,6 最后对整个序列进行扫尾直接插入排 序,从而完成排序 1229323434456478 北真大学张铭编写

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 Θ(n Θ(n) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 最差情 ) 况 Θ(n Θ(n) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 平均情 ) 况 最佳情 0 Θ(n) Θ(n) 0 0 Θ(n) 况 选择 排序 改进 的冒 泡排 序 冒泡 排序 二分 法插 入排 序 改进的 插入排 序 直接 插入 排序 移动次 数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 最差情 ) 况 Θ(n2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 Θ(n ) 2 平均情 ) 况 Θ(n2 Θ(n Θ(n) ) 2 最佳情 Θ(n) Θ(n) Θ(nlog n) ) 况 选择 排序 改进的 冒泡排 序 冒泡 排序 二分法 插入排 序 改进的 插入排 序 直接 插入 排序 总代价 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 原因 „ 一个长度为n序列平均有 n(n-1)/4 对逆置 „ 任何一种只对相邻记录进行比较 的排序算法的平均时间代价都是 Θ(n2) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 7.3 Shell排序 „ 直接插入排序的两个性质： „ 在最好情况（序列本身已是有序 的）下时间代价为Θ(n) „ 对于短序列，直接插入排序比较 有效 „ Shell排序有效地利用了直接插 入排序的这两个性质 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 Shell排序 „ 算法思想： „ 先将序列转化为若干小序列，在这些 小序列内进行插入排序 „ 逐渐扩大小序列的规模，而减少小序 列个数，使得待排序序列逐渐处于更 有序的状态 „ 最后对整个序列进行扫尾直接插入排 序，从而完成排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 d=4 45 34 78 12 34 32 29 64 d=2 34 32 29 12 45 34 78 64 d=1 29 12 34 32 45 34 78 64 12 29 32 34 34 45 64 78

增量每次除以2递减”的 she排序 plate old Shelsorter: Sort Record, class Compare> class shells (Record array], int n) Sorter //She排序, Array[]为待排序数组, /n为数组长度 /增deta每次除以2递减 /针对变化的增量而修改的插入排序算法,参数 //deta表示当前的增量 for (int delta=n/2; delta>0; delta/=2) oid ModifiedInsertsort(Record Array, //分别对deta个子序列排序 int n, int delta); for (int j=O; j void Shell Sorter: ■不稳定 ModifiedInsertsort((Record Array [l,int n, int 空间代价:⊙(1) ∥参数deta表示当前的增量 ∥/对子序列中第个记录排序 ■增量每次除以2递减,时间代 for(int i=delta; i=delta; j-=delta) if( Compare: It(Array[], Array [j-delta])) ■选择适当的增量序列,可以使得 wap(Array j, j-delta); 时间代价接近e(m) 老真大儿聊张铭写 版叔斯有就即究 真大影张帖写 叔新有,量究 shel排序选择增量序列 ■增量每次除以2递减”时,效率仍 ■ Hibbard增量序列 然为e(n2) 2k-1, ■问题:选取的增量之间并不互质 aShe(3)和 Hibbard增量序列的 间距为2k4的子序列都是由那些间 she排序的效率可以达到e(m3/2) 距为2的子序列组成的 ■选取其他增量序列还可以更进一步 上一轮循环中这些子序列都已经 减少时间代价 排过序了,导致处理效率不高 北真大学张铭编写 聊张帖写 权新有,究

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 “增量每次除以2递减”的 Shell排序 template class ShellSorter:public Sorter { //Shell排序类 private: // 针对变化的增量而修改的插入排序算法，参数 //delta表示当前的增量 void ModifiedInsertSort(Record Array[], int n,int delta); public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 template Void ShellSorter::Sort (Record Array[], int n) { //Shell排序，Array[]为待排序数组， // n为数组长度 // 增量delta每次除以2递减 for (int delta=n/2; delta>0; delta/=2) //分别对delta个子序列排序 for (int j=0; j void ShellSorter:: ModifiedInsertSort((Record Array[],int n, int delta) { // 参数delta表示当前的增量 // 对子序列中第i个记录排序 for (int i=delta; i=delta; j-=delta){ if (Compare::lt(Array[j], Array[j-delta])) swap(Array, j, j-delta); else break; } } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 算法分析 „ 不稳定 „ 空间代价：Θ(1) „ 增量每次除以2递减，时间代 价：Θ(n2) „ 选择适当的增量序列，可以使得 时间代价接近Θ(n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 Shell排序选择增量序列 „ 增量每次除以2递减”时，效率仍 然为Θ(n2) „ 问题：选取的增量之间并不互质 „ 间距为2k-1的子序列都是由那些间 距为2k的子序列组成的 „ 上一轮循环中这些子序列都已经 排过序了，导致处理效率不高 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 „ Hibbard增量序列 „ {2k -1，2k-1 -1，…，7，3，1}， „ Shell(3)和Hibbard增量序列的 Shell排序的效率可以达到Θ(n3/2) „ 选取其他增量序列还可以更进一步 减少时间代价

74基于分治法的排序 分治策略的基本思想 将原始数组分为若干个子部分然 ■分治策略的实例 后分别进行排序 BST査找、插入、删除算法 快速排序、归并排序 两种算法 二分检索 快速排序 主要思想 划分 归并排序 求解子问题(子问题不重叠) 综合解 举位▲张倍墙写 北大单张铭写 叔新有,命邮 Divide-and-Conquer(P)t //问题足够小了就面接求解 if i Pl s cthen <SP; return; y 20世纪十大算法( Computing in //问题过大就分解成子问题 7. 1962London A] Elliot Brothers divide pinto阿,P Ld的 Tony Hoare提出的快速排 角1对子问题分别求解(此处利用递归调 序 for i=1 to k i= Divide-and-Conquer( Pi /综合子问题的解成为问题的解 return Merge(y,y,…y 北真大张写 真大影张帖写 叔新有,量究 253445图 T122964 74.1快速排序 32 ■算法思想 选择轴值( pivot) 将序列划分为两个子序列L和R, 囡 45团6 使得L中所有记录都小于或等于轴 值,R中记录都大于轴值 对子序列L和R递归进行快速排序 最终撸序结果: 122529 34456478 北真大学张铭编写

10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 7.4 基于分治法的排序 „ 将原始数组分为若干个子部分然 后分别进行排序 „ 两种算法 „ 快速排序 „ 归并排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 分治策略的基本思想 „ 分治策略的实例 „ BST查找、插入、删除算法 „ 快速排序、归并排序 „ 二分检索 „ 主要思想 „ 划分 „ 求解子问题(子问题不重叠) „ 综合解 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 Divide-and-Conquer(P) { //问题足够小了就直接求解 if |P| ≤ c then {S(P); return; } //问题过大就分解成子问题 divide P into P1, P2, …, Pk //对子问题分别求解（此处利用递归调 用） for i = 1 to k yi = Divide-and-Conquer(Pi) //综合子问题的解成为问题的解 return Merge(y1, y2, …, yk) } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 „ 20世纪十大算法 ( Computing in „ 7. 1962London的Elliot Brothers Ltd的Tony Hoare提出的快速排 序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 7.4.1 快速排序 „ 算法思想： „ 选择轴值（pivot） „ 将序列划分为两个子序列L和R， 使得L中所有记录都小于或等于轴 值，R中记录都大于轴值 „ 对子序列L和R递归进行快速排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 最终排序结果： 12 25 29 32 34 45 64 78 25 34 45 32 78 12 29 64 25 12 29 29 34 45 78 64 12 25 29 34 78 64 32 45 25 64 78