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

数据结构与算法 大纲 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 <class Record class compare> ■总的排序类 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 x<yil 排序码进行比较 static bool eq(int x, int y) return x==yi] static bool gt (int x, int y return x>yi] ■为了简便起见,本教材讨论整数 tatic bool le int x, int y ireturn x<=yil 排序的例子 static bool ge int x,int y ireturn x>=yi] 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 swap函数 PrintArray函数 template <class Record, class Compare> template <class record, class Compare> void Sorter<Record Compare> void Sorter<Record, Compare> 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 Record,class Compare> 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 x<y;} static bool eq(int x,int y) {return x==y;} static bool gt(int x,int y) {return x>y;} static bool le(int x,int y) {return x<=y;} static bool ge(int x,int y) {return x>=y;} }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 swap函数 template <class Record,class Compare> void Sorter<Record,Compare>:: swap(Record Array[],int i,int j) { //交换数组中的两个元素 Record TempRecord = Array[i]; Array[i] = Array[j]; Array[j] = TempRecord; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 PrintArray函数 template <class Record,class Compare> void Sorter<Record,Compare>:: 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 <class Record, class Compare> =134.4578123432296 wpid StraightInsertSorter<Record, Compare> 4 ‖1234322964 /Aray[]为待排序数组,n为数组长度 i=312344578|332296 for(inti=1;i<ni++)∥/依次插入第个记录 ∥/依次与前面的记录进行比较,发现逆置就交换 for (int j=i;j>O;j--)t i=412342.4578‖322964 if (Compare: : lt(Array D], Array[-1]) =5123234344578‖2964 else break;//此时前面记录已排序 i=7122932343445478‖ 大张帖写 叔新有,量究 算法分析 优化的插入排序算法 稳定 uplate <class Record, class 空间代价:e(1) Compare> 时间代价: class ImprovedInsertsorter: public 最佳情况:n-1次比较,0次交换,e(n) Insertsorter<Record, Compare> 最差情况:比较和交换次数为 //优化的插入排序类 ∑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 <class Record,class Compare> void StraightInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 for (int i=1; i<n; i++) // 依次插入第i个记录 { //依次与前面的记录进行比较，发现逆置就交换 for (int j=i;j>0;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 Record,class Compare> class ImprovedInsertSorter:public InsertSorter<Record,Compare> { //优化的插入排序类 public: void Sort(Record Array[],int n); };

template <class Record, class Compare> void ImprovedInsertsorter<Record, Compare> Sort(Record Arrayal, int n) ∥/Aray[]为待排序数组,n为数组长度 二分法插入排序 Record TempRecord临时变量 for(inti=1i<ni++){//依次插入第个记录 算法思想: /从i始往前寻找记录的正确位量 在插入第个记录时,前面的记录 /将那些大于等于记录记录后移 已经是有序的了 Compare: It(TempRecord, Array[]))& 可以用二分法查找第i个记录的正 Array U+1]= Array u] 确位置 时后面就是记录的正确位量,回填 y[+1]=Ter 举▲张铭物写 北大单张铭写 叔新有,命邮 算法分析 722冒泡排序 稳定 间代价:e(1) 算法思想: ■时间代价: 不停地比较相邻的记录,如果不 插入每个记录需要e(og次比较 满足排序要求,就交换相邻记 最多移动i+1次,最少2次(移动临时记 录,直到所有的记录都已经排好 序 因此最佳情况下总时间代价为 e( nlog n),最差和平均情况下仍为e(n2) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 4534781234322964 ⊥=11245347829343264 冒泡排序类 122 453478 template <class Record class Compare> 4 class BubbleSorter: public 2932a445348 Sorter<Record, compare> //冒泡排序类 i=51229323434456478 void Sort(Record Array [ int n); i=6 1229323434456478 71229323434456478 聊张帖写 权新有,究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 template <class Record,class Compare> void ImprovedInsertSorter<Record,Compare>:: Sort(Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量 for (int i=1; i<n; i++) { // 依次插入第i个记录 TempRecord=Array[i]; //从i开始往前寻找记录i的正确位置 int j = i-1; //将那些大于等于记录i的记录后移 while ((j>=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 Record,class Compare> class BubbleSorter:public Sorter<Record,Compare> { //冒泡排序类 public: void Sort(Record Array[],int n); };