2525 49 16 08 0 2 5 I=3 Gap=1 49 16 25 开始时gap的值较大,子序列中的对象较少, 排序速度较快;随着排序进展,gap值逐渐 变小,子序列中对象个数逐渐变多,由于前 面工作的基础,大多数对象已基本有序,所 以排序速度仍然很快。 16
16 21 25 49 16 25* 08 0 1 2 3 4 5 21 i = 3 08 Gap = 1 16 25 49 25* ◼ 开始时 gap 的值较大, 子序列中的对象较少, 排序速度较快; 随着排序进展, gap 值逐渐 变小, 子序列中对象个数逐渐变多, 由于前 面工作的基础, 大多数对象已基本有序, 所 以排序速度仍然很快
希尔排序的算法 typedef int SortData void ShellSort( Sort Data VIl intn)i SortData temp; int gap=n/2;/gap是隔 while( gap=0)t ∥循环,直到gap为零 for( int i= gap; i<n; 1++t temp=vi; ∥直接插入排序 for(int j=1;j>=gap;jj-gap) if( temp VLj-gap]) Vul=VU-gapl; else break: 17
17 希尔排序的算法 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 对特定的待排序对象序列,可以准确地估算 排序码的比较次数和对象移动次数。 18
18 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的范围内。 这是在利用直接插入排序作为子序列排序 方法的情况下得到的
19 ◼ 想要弄清排序码比较次数和对象移动次数 与增量选择之间的依赖关系，并给出完整 的数学分析，还没有人能够做到。 ◼ 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和Ⅴ团 20
20 交换排序 ( 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)