∥-趟希尔排序按间隔划分子序列 void ShellInsert(SqList &L, int gap)i for (int i-=gap+l; K<=L length; ++if if (ltL ri]. key, L. ri-gap] key)) L r=.ri for(int j=l-gap ]>0 & LTL r[o]. key, L r[]. key);j-=gap) L rLj+gap=.rLI ) Lrli+gap]=L r[OI
//一趟希尔排序,按间隔dk划分子序列 void ShellInsert(SqList &L, int gap){ for (int i=gap+1;i<=L.length;++i){ if (LT(L.r[i].key,L.r[i-gap].key)){ L.r[0]=L.r[i]; for (int j=i-gap;j>0 && LT(L.r[0].key,L.r[j].key); j-=gap) L.r[j+gap]=L.r[j]; L.r[j+gap]=L.r[0]; } } }
算法分析 对特定的待排序对象序列,可以准确地估算 关键字的比较次数和对泉移动次数。 但想要弄清关键字比较次数和对象移动次数 与增量选择之间的依赖关系,并给出完整的 数学分析,还没有人能够做到。 gp的取法有多种。最初shel提出取gqp= n2」J,gq=lgqp/2」,直到gq=1。后来 Knuth提出取gq=Lgqp/3」+1。还有人提出 都取奇数为好,也有人提出各g互质为好。 其他取法:教材p272倒数第二段
算法分析 对特定的待排序对象序列，可以准确地估算 关键字的比较次数和对象移动次数。 但想要弄清关键字比较次数和对象移动次数 与增量选择之间的依赖关系，并给出完整的 数学分析，还没有人能够做到。 gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。后来 Knuth 提出取gap = gap/3 +1。还有人提出 都取奇数为好，也有人提出各gap互质为好。 其他取法：教材p272 倒数第二段
Knuth利用大量的实验统计资料得出,当n 很大时,关键字平均比较次数和对象平均移 动次数大约在n125到1.6n125的范围内。这 是在利用直接插入排序作为子序列排序方法 的情况下得到的
Knuth利用大量的实验统计资料得出，当 n 很大时，关键字平均比较次数和对象平均移 动次数大约在 n 1.25 到 1.6n 1.25 的范围内。这 是在利用直接插入排序作为子序列排序方法 的情况下得到的
交换排序( Exchange Sort) 交换排序的基本思想是两两比较待排序对象的关 键字,如果发生逆序即排列顺序与排序后的次序 正好相反),则交换之,直到所有对象都排好序为 起泡排序( Bubble sort) 起泡排序的基本方法是:设待排序对象序列中 的对象个数为n。最多作n-1趟排序。在第i 趟中顺次两两比较1K和rKe,j=i, 。…。如果发生逆序,则交换r和 i+I
交换排序 ( Exchange Sort ) 起泡排序的基本方法是：设待排序对象序列中 的对象个数为 n。最多作 n-1 趟排序。在第 i 趟中顺次两两比较r[j-1].Key和r[j].Key，j = i, i+1, , n-i-1。如果发生逆序，则交换r[j-1]和 r[j]。 交换排序的基本思想是两两比较待排序对象的关 键字，如果发生逆序(即排列顺序与排序后的次序 正好相反)，则交换之，直到所有对象都排好序为 止。 起泡排序 (Bubble Sort)
21 25 49 25 6 08 0 2 5 49 08 chiang- 2剧剧回 49 6825 chang=1 i=3 21108-25257 chang=1
21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 49 25 16 49 chang=1 08 25* chang=1 i = 2 i = 3 16 08 chang=1 21 25 25* 49 21 25 16 08