排序码比较次数:当n较大时,总排序 码比较次数比直接插入排序的最坏情 况要好得多,但比其最好情况要差。 n对象移动次数:折半插入排序的对象移 动次数与直接插入排序相同,依赖于对 象的初始排列
◼ 排序码比较次数: 当 n 较大时, 总排序 码比较次数比直接插入排序的最坏情 况要好得多, 但比其最好情况要差。 ◼ 对象移动次数: 折半插入排序的对象移 动次数与直接插入排序相同, 依赖于对 象的初始排列
4希尔排序( Shell Sort) 希尔排序方法又称为缩小增量排序。 基本思想 ◆设待排序对象序列有n个对象,首先取一个整数 gap<n作为间隔,将下标相差为gap的倍数对象 放在一组。 ◆在组内作插入排序。 ◆然后缩小间隔gap,例如取gap=「gap21,重复上 述的组划分和排序工作。直到最后取gap=1, 将所有对象放在同一个组中进行排序为止。 例:9,14,28,31,2,7,46,70,62,180,30,82,170,5,9
4.希尔排序 (Shell Sort) ◼ 希尔排序方法又称为缩小增量排序。 ◼ 基本思想 : 设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将下标相差为gap的倍数对象 放在一组。 在组内作插入排序。 然后缩小间隔 gap, 例如取 gap = gap/2，重复上 述的组划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个组中进行排序为止。 ✓例：99,14,28,31,2,7,46,70,62,180,30,82,170,5,9
希尔排序的算法 template <class type> void datalist<Type>: ShellSOrt(t Element<Type>temp; int gap = Currentsize/2;/gap是子序列间隔 while( ga ap!=0){/循环直到gap为零 for (int i= gap i< CurrentSize; 1++)i temp= Vector[i;接插入排序 for( int j=1;>=gap; j-=gap if( temp< Vectorlj-gap)) Vector lj]= vector[i-gap]; se breaK
希尔排序的算法 template <class Type> void dataList<Type> :: ShellSort ( ) { Element<Type> temp; int gap = CurrentSize / 2; //gap是子序列间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < CurrentSize; i++) { temp = Vector[i]; //直接插入排序 for ( int j = i; j >= gap; j -= gap ) if ( temp < Vector[j-gap] ) Vector[j] = Vector[j-gap]; else break;
ector = temp gap=( int ) gap /2); Gap的取法有多种。最初she提出取gap Ln/2」,gap=Lgap/2」,直到gap=1。 Knuth 提出取gap=Lgap3+1。还有人提出都取 奇数为好,也有人提出各gap互质为好 对特定的待排序对象序列,可以准确地估算 排序码的比较次数和对象移动次数
Vector[j] = temp; } gap = ( int ) ( gap / 2 ); } } ◼ Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。Knuth 提出取 gap = gap/3 +1。还有人提出都取 奇数为好，也有人提出各gap 互质为好。 ◼ 对特定的待排序对象序列，可以准确地估算 排序码的比较次数和对象移动次数
。想要弄清排序码比较次数和对象移动次数与 增量(gap)选择之间的依赖关系,并绐出 完整的数学分析,还没有人能够做到。 Knuh利用大量实验统计资料得出:当n很 大时,排序码平均比较次数和对象平均移动 次数大约在n1235到1.6n125的范围内。这是 在利用直接插入排序作为子序列排序方法的 情况下得到的
◼ 想要弄清排序码比较次数和对象移动次数与 增量（gap）选择之间的依赖关系，并给出 完整的数学分析，还没有人能够做到。 ◼ Knuth利用大量实验统计资料得出 : 当 n 很 大时，排序码平均比较次数和对象平均移动 次数大约在 n 1.25 到 1.6n 1.25 的范围内。这是 在利用直接插入排序作为子序列排序方法的 情况下得到的