希尔排序

in 数据结构 with 1 comment

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

排序思路

先取一个小于n的整数d1作为第一个增量,把表的全部元素分为d1个组,将所有距离为d1的倍数的元素放在同一个组中,在各组内进行直接插入排序;

取第二个增量d2(<d1),重复上述的分组和排序,直至所取增量dt=1(dt<dt-1<...<d2<d1),此时所有元素放在同一组中进行直接插入排序。

排序过程中,增量严格递减至1,所以希尔排序又被称为递减增量排序

但是,步长序列(dt,...,d1)的选取,目前仍无定论。

通常我们选取

$$ d_1=n/2,d_{i+1}=\lfloor d_i/2\rfloor $$

分组情况图示:

组数 元素
第1组 R[0] R[d] ... R[kd]
第2组 R[1] R[d+1] ... R[kd+1]
第3组 R2] R[d+2] ... R[kd+2]
... ... ... ... ...
第d组 R[d-1] R[2d-1] ... R[(k+1)d-1]

排序算法

以c为例,从小到大排序,步长按上述选取

#include<stdio.h>

void shell_sort(int R[],int n){
    int i,j,d,tmp;
    d=n/2;
    while(d>0){

         //打印步长为d后排序前的结果
        printf("%d: ",d);
        int k;
        for (k = 0; k < n;k++){
            printf("%d ", R[k]);
        }
        
        printf("\n");
        for(i=d;i<n;i++){
            tmp=R[i];
            j=i-d;//直接插入排序
            while(j>=0&&tmp<R[j]){
                R[j+d]=R[j];
                j=j-d;
            }
            R[j+d]=tmp;
        }
        d=d/2;
    }
}
int main(void){
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    shell_sort(a, 10);
}

输出结果:

5: 9 8 7 6 5 4 3 2 1 0
2: 4 3 2 1 0 9 8 7 6 5
1: 0 1 2 3 4 5 6 7 8 9

算法分析

时间复杂度:

希尔排序的时间复杂度与其所选取的增量序列有关,一般认为其平均时间复杂度为O(n^1.3^)

空间复杂度:

只使用了i,j,d,tmp四个辅助变量,与问题规模n无关。空间复杂度为O(1)

稳定性:

相同元素的相对位置可能改变,这是一种不稳定的排序方法。

复杂性:

较复杂

归位:

在最后一趟排序结束前,所有元素并不一定归位。

Responses
  1. study 一起学习 go

    Reply