冒泡排序算法 算法分析 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) 北真大学张铭编写 聊张帖写 权新有,究 66 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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)