当n较大时,总排序码比较次数比直接插入 排序的最坏情况要好得多,但比其最好情况 要差。 在对象的初始排列已经按排序码排好序或 接近有序时,直接插入排序比折半插入排序 执行的排序码比较次数要少。折半插入排 序的对象移动次数与直接插入排序相同,依 赖于对象的初始排列 折半插入排序是一个稳定的排序方法。 折半插入排序的时间复杂度为o(m2)
◼ 当 n 较大时, 总排序码比较次数比直接插入 排序的最坏情况要好得多, 但比其最好情况 要差。 ◼ 在对象的初始排列已经按排序码排好序或 接近有序时, 直接插入排序比折半插入排序 执行的排序码比较次数要少。折半插入排 序的对象移动次数与直接插入排序相同, 依 赖于对象的初始排列。 ◼ 折半插入排序是一个稳定的排序方法。 ◼ 折半插入排序的时间复杂度为o(n2 )
希尔排序( Shell sort 基本思想设待排序对象序列有n个对象,首 先取一个整数gap<n作为间隔,将全部对 象分为gap个子序列,所有距离为gap的对 象放在同一个子序列中,在每一个子序列中 分别施行直接插入排序。然后缩小间隔gap, 例如取gap=「gap/21,重复上述的子序列划 分和排序工作。直到最后取gap==1,将所 有对象放在同一个序列中排序为止。 希尔排序方法又称为缩小增量排序
希尔排序 (Shell Sort) ◼ 基本思想设待排序对象序列有n 个对象, 首 先取一个整数 gap < n 作为间隔, 将全部对 象分为 gap 个子序列, 所有距离为 gap 的对 象放在同一个子序列中, 在每一个子序列中 分别施行直接插入排序。然后缩小间隔gap, 例如取 gap = gap/2，重复上述的子序列划 分和排序工作。直到最后取 gap == 1, 将所 有对象放在同一个序列中排序为止。 ◼ 希尔排序方法又称为缩小增量排序
希尔排序过程 3( 25)(49)②5 08 Gap=3 e6e的的 49 Gap=2 16)08)②25”(25)(49 08 25 49 I=1 08 21)②25 49 Gap=1 5)(49
i = 3 Gap = 3 0 1 2 3 4 5 21 25 49 25* 16 08 0 1 2 3 4 5 21 16 08 25* 25 49 i = 2 Gap = 2 21 16 08 25* 25 49 08 16 21 25* 25 49 i = 1 Gap = 1 08 16 21 25* 25 49 08 16 21 25* 25 49 希尔排序过程
希尔排序的算法 typedef int SortData void ShellSort( SortData VI, int n)& SortData temp; int gap=n/2;gap是间隔 while(gap!=0){/循环,直到gap为零 for(int i=gap; i< n; i++) temp=V; /直接插入排序 for(intj=i;j>=gap;j=j-gap) if( temp< vli-gap) v[il=Ⅴj-gapl; else break v前=temp; gap=(int)( gap /2);
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; V[j] = temp; } gap = ( int ) ( gap / 2 ); } } 希尔排序的算法
开始时gap的值较大,子序列中的对象较少,排序速度 较快;随着排序进展,gap值逐渐变小,孑序列中对象 个数逐渐变多,由于前面大多数对象已基本有序,所 以排序速度仍然很快 Gap的取法有多种。she提出取gap=Ln/2」,gap= gap/2」,直到gap=1 对特定的待排序对象序列,可以准确地估算排序码的 比较次数和对象移动次数。 希尔排序所需的比较次数和移动次数约为n13 当n趋于无穷时可减少到nog2)2
◼ 开始时 gap 的值较大, 子序列中的对象较少, 排序速度 较快; 随着排序进展, gap 值逐渐变小, 子序列中对象 个数逐渐变多, 由于前面大多数对象已基本有序, 所 以排序速度仍然很快。 ◼ Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 ◼ 对特定的待排序对象序列，可以准确地估算排序码的 比较次数和对象移动次数。 ◼ 希尔排序所需的比较次数和移动次数约为n 1.3 当n趋于无穷时可减少到n(log2 n ) 2