希尔排序的算法 template <class Type> void Shellsort( datalist<Type> list) int gap= list. CurrentSize /2 ∥!qp是子序列间隔 whille( gap)i ∥循环直到gqp为零 ShellInsert(list,gqp);∥-趟直接插入排序 8ep=8ep==2?1:(int)(gqp2.2);∥修改
template <class Type> void Shellsort ( datalist<Type> & list ) { int gap = list.CurrentSize / 2; // gap 是子序列间隔 while ( gap ) { //循环,直到gap为零 ShellInsert ( list, gap ); //一趟直接插入排序 gep = gep == 2 ? 1 : ( int ) ( gap/2.2 ); //修改 } }
template <class Type> void shelllnsert( datalist<Type>& list; const int gep)i ∥-趟希尔排序,按间隔gqp划分子序列 for (int i=gap; i< list. CurrentSize; i++)t Element<Type> temp= list. Vector[i]; intj=i; while (>= gap && temp. getKeyo< list. Vector -].getKey o)i list. Vector]= list. Vectorli gapl v gap list. Vector]=temp;
template <class Type> void shellInsert ( datalist<Type> & list; const int gep ) { //一趟希尔排序,按间隔gap划分子序列 for ( int i = gap; i < list.CurrentSize; i++) { Element<Type> temp = list.Vector[i]; int j = i; while ( j >= gap && temp.getKey ( ) < list.Vector[j-gap].getKey ( ) ) { list.Vector[j] = list.Vector[j-gap]; j -= gap; } list.Vector[j] = temp; } }
Gqp的取法有多种。最初shel提出取gp= Lm/2,gq= Gap/2J,直到qp=1。后来 knuth提出取gqp=Lgqp/3」+1。还有人提出 都取奇数为好,也有人提出各gp互质为好。 算法分析 对特定的待排序对象序列,可以准确地估算 关键码的比较次数和对象移动次数。 但想要弄清关键码比较次数和对象移动次数 与增量选择之间的依赖关系,并给出完整的 数学分析,还没有人能够做到
Knuth利用大量的实验统计资料得出,当n 很大时,关键码平均比较次数和对象平均移 动次数大约在n125到1.6n125的范围内。这 是在利用直接插入排序作为子序列排序方法 的情况下得到的
交换排序( Exchange Sort) 交换排序的基本思想是两两比较待排序对象的关 键码,如果发生逆序(即排列顺序与排序后的次 序正好相反),则交换之,直到所有对象都排好 序为止。 起泡排序( Bubble sort n起泡排序的基本方法是:设待排序对象序列中 的对象个数为n。最多作n-1趟,i=1,2, n-2。在第i趟中顺次两两比较vm-广1Ke和 vn-i.Key,j=n-1,n-2,…,i。如果发生逆序 则交换vm1和vm引