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