增量每次除以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) „ 选取其他增量序列还可以更进一步 减少时间代价