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

冒泡排序算法 算法分析 template <class Record, class Compare> void Bubble Sorter<Record, Compare>:: 稳定 Sort( Record array[, int n) //冒泡排序,Aray[]为待排数组,n为数组长度 空间代价:e(1) /第个记录冒泡 ■时间代价 for(int i=l; i<n; i++) 比较次数∑(n-1)=m(n-1)/2=6(m2 依次比较相邻记录,如果发现逆置,就交换 for(int j=n-l; j>=i; j-) 交换次数最多为e(n2),最少为0,平均 if (Compare: lt(Array l, Array l-1]) 为e(n2)。 swap(Array, j, j-1); 最大,最小,平均时间代价均为e(n2)。 } 举位▲张倍墙写 北大单张铭写 叔新有,命邮 优化的冒泡排序 优化的冒泡排序 改进:检查每次冒泡过程中是否 emplate <class Record, class 发生过交换,如果没有,则表明 Compare> 整个数组已经排好序了,排序结 class Improved BubbleSorter: public Sorter<Record, Compare> 束 //优化的冒泡排序类 避免不必要的比较 public: void Sort (Record array lint n) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 template <class Record, class compare> void Improved Bubble Sorter<Record, Compare> 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 <class Record,class Compare> void BubbleSorter<Record,Compare>:: Sort(Record Array[], int n) { //冒泡排序，Array[]为待排数组，n为数组长度 //第i个记录冒泡 for (int i=1; i<n; i++) //依次比较相邻记录，如果发现逆置，就交换 for (int j=n-1; j>=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 Record,class Compare> class ImprovedBubbleSorter:public Sorter<Record,Compare> { //优化的冒泡排序类 public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 template <class Record,class Compare> void ImprovedBubbleSorter<Record,Compare>:: Sort(Record Array[], int n) { bool NoSwap; // 是否发生交换的标志 for (int i=1; i<n; i++) { NoSwap = true; // 标志初始为真 for (int j=n-1; j>=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 <dass Record, class Compare Void Straightselectsorter<Record, Compare>: 直接选择排序 Sort(Record Array ll, int n) 依次选出第小的记录,即剩余记录中最小的那个 template <class record, class for(int i=0; i<n-1; i++)t 首先假设记录就是最小的 Compare> class Straightselectsorter:public /开始向后扫描所有剩余记录 Sorter<Record Compare> ∥/如果发现更小的记录,记录它的位置 /直接选择排序类 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 Record,class Compare> class StraightSelectSorter:public Sorter<Record,Compare> { //直接选择排序类 public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 template <class Record,class Compare> Void StraightSelectSorter<Record,Compare>:: 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 <class record, class Compare> old Shelsorter<Record, Compare>: Sort Record, class Compare> class shells (Record array], int n) Sorter<Record, Compare> //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<delta; j++) ModifiedInsertsort(&Array ll, n-j,delta) void Sort(Record Array ll, int n ); 举位▲张倍墙写 北大单张铭写 叔新有,命邮 针对变化的增量而修改的 插入排序算法 算法分析 template <class Record, cass Compare> void Shell Sorter<Record, Compare>: ■不稳定 ModifiedInsertsort((Record Array [l,int n, int 空间代价:⊙(1) ∥参数deta表示当前的增量 ∥/对子序列中第个记录排序 ■增量每次除以2递减,时间代 for(int i=delta; i<n; i+=delta) 价:e for(int j=i; j>=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 Record,class Compare> class ShellSorter:public Sorter<Record,Compare> { //Shell排序类 private: // 针对变化的增量而修改的插入排序算法，参数 //delta表示当前的增量 void ModifiedInsertSort(Record Array[], int n,int delta); public: void Sort(Record Array[],int n); }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 template <class Record,class Compare> Void ShellSorter<Record,Compare>::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<delta; j++) ModifiedInsertSort(&Array[j], n-j,delta); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 针对变化的增量而修改的 插入排序算法 template <class Record,class Compare> void ShellSorter<Record,Compare>:: ModifiedInsertSort((Record Array[],int n, int delta) { // 参数delta表示当前的增量 // 对子序列中第i个记录排序 for (int i=delta; i<n; i+=delta) for (int j=i; j>=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