是熊是猫溜溜

子非鱼，焉知鱼之乐

希尔排序

发表于 更新于 分类于
本文字数： 753 阅读时长 ≈ 1 分钟

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。根据设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。

主要思想

假定步长为h，则把数组分为h组，从前往后间隔h的元素为一组。先在组内进行插入排序，保证每个组内是有序的，再按照步长为1进行一次全面插入排序，从而得到有序数组。

原数据：

1
[9] [8] [7] [1] [3] [5]

第一步，假设h为3，则根据规则原数组分为如下三组

1
[9] [1]
1
[8] [3]
1
[7] [5]

第二步，在三个小组内，分别进行插入排序，得到三个有序子数组。

1
[1] [9]
1
[3] [8]
1
[5] [7]

第三步，三个子数组按照原来的位置存放，得到第一轮排序后的数组。

1
[1] [3] [5] [9] [8] [7]

第四步，按照步长为[1]进行一次插入排序，即可得到有序数组。

1
[1] [3] [5] [7] [8] [9]

时间与空间复杂度

希尔排序是一个不稳定的排序算法，其最好情况下时间复杂度为O(n)，最坏情况下时间复杂度为2^n，平均时间复杂度为2^n，空间复杂度为O(!)。时间复杂度计算公式如下。

$$
待补充
$$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void Shell(Comparable[] c){
    int N = c.length;
    int h = 1;
    while(h < N / 3){
        h = 3 * h + 1;
    }
    while (h >= 1){
        for(int i = h; i < N; i++){
            for(int j = i; j >= h && less(c[j], c[j-h]); j -= h){
                exch(c, j, j-h);
            }
        }
        h = h / 3;
    }
}