希尔排序的算法 typedef int SortData void ShellSort( Sort Data VI intn i SortData temp; int gap=n/2;∥gap是间隔 while( gap=0)t ∥循环,直到gap为零 for( int 1= gap; i <n; 1++t temp=V[; ∥/直接插入排序 for( intj=i;j>=gap;j=j-gap if( temp VLj-gap]) Vul=VU-gap; else break:
21 希尔排序的算法 typedef int SortData; void ShellSort ( SortData V[ ], int n ) { SortData temp; int gap = n / 2; //gap是间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < n; i++) { temp = V[i]; //直接插入排序 for ( int j = i; j >= gap; j = j-gap ) if ( temp < V[j-gap] ) V[j] = V[j-gap]; else break;
VlI=temp gap=( int)( gap/2 ); Gap的取法有多种。最初shel提出取gap= Ln2,gap=Lgap/2,直到gap=1。 knuth 提出取gap=Lgap3+1 对特定的待排序对象序列,可以准确地估算 排序码的比较次数和对象移动次数。 22
22 V[j] = temp; } gap = ( int ) ( gap / 2 ); } } ◼ Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。 ◼ 对特定的待排序对象序列，可以准确地估算 排序码的比较次数和对象移动次数
想要弄清排序码比较次数和对象移动次数 与增量选择之间的依赖关系,并给出完整 的数学分析,还没有人能够做到。 Knuth利用大量实验统计资料得出:当n 很大时,排序码平均比较次数和对象平均 移动次数大约在n125到1.6n125的范围内。 这是在利用直接插入排序作为子序列排序 方法的情况下得到的
23 ◼ 想要弄清排序码比较次数和对象移动次数 与增量选择之间的依赖关系，并给出完整 的数学分析，还没有人能够做到。 ◼ Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和对象平均 移动次数大约在 n 1.25到 1.6n 1.25的范围内。 这是在利用直接插入排序作为子序列排序 方法的情况下得到的
交换排序( Exchange Sort) 基本思想是两两比较待排序对象的排序码如 发生逆序(即排列顺序与排序后的次序正好相 反),则交换之。直到所有对象都排好序为止。 起泡排序( Bubble sort 基本方法:设待排序对象序列中的对象个 数为n。最多作n-1趟,i=1,2,,.n-1。 在第i趟中从后向前,j=n-1,n-2,…,i 顺次两两比较V-1和V。如果发生逆序, 则交换V1和Ⅴ团 24
24 交换排序 ( Exchange Sort ) ◼ 基本方法：设待排序对象序列中的对象个 数为 n。最多作 n-1 趟, i = 1, 2, , n-1。 在第 i 趟中从后向前，j = n-1, n-2, , i， 顺次两两比较V[j-1]和V[j]。如果发生逆序， 则交换V[j-1]和V[j]。 基本思想是两两比较待排序对象的排序码,如 发生逆序(即排列顺序与排序后的次序正好相 反)，则交换之。直到所有对象都排好序为止。 起泡排序 (Bubble Sort)
49 21 25 25 6| 2 3 5 chiang- i=2 国 25 49 08 16 5 Exchang=1 i=3 49 21 25 08 16 Exchang=
25 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 49 16 25 25 16 08 49 Exchang=1 08 25* 49 21 Exchang=1 i = 2 i = 3 08 16 Exchang=1 21 25 25*