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