思路流程

插入排序的变形，在基本有序的情况下，插入排序性能很好

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以 步长为5 开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再 以3为步长 进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

代码

public class ShellSort {
    public static void main(String[] args) {
        int[] toBeSorted = { 0, 1, 3, 5, 2, 4, 6, 0, -1 };

        for (int gap = toBeSorted.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < toBeSorted.length; i++) {
                for (int j = i - gap; j >= 0 && toBeSorted[j] > toBeSorted[j + gap]; j -= gap) {
                    int t = toBeSorted[j];
                    toBeSorted[j] = toBeSorted[j + gap];
                    toBeSorted[j + gap] = t;
                }
            }
        }

        for (int p = 0; p < toBeSorted.length; p++) {
            System.out.print(toBeSorted[p]);
        }
        System.out.println();
    }
}

时间复杂度

最优时间复杂度O(n),根据步长设置不同而不同。

稳定性

不稳定