图解Java排序算法之希尔排序

图解Java排序算法之希尔排序：完整攻略

什么是希尔排序

希尔排序（Shell Sort），又称递减增量排序法，是插入排序的一种更高效的改进版本。希尔排序是将整个序列分成若干子序列，对于每个子序列进行直接插入排序，减小增量再次排序，循环直至增量为1。

希尔排序的原始实现

首先看一下希尔排序的原始实现（不采用递归实现）：

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            for (int j = i; j >= gap && arr[j - gap] > arr[j]; j -= gap) {
                // 交换位置
                int temp = arr[j];
                arr[j] = arr[j - gap];
                arr[j - gap] = temp;
            }
         }
    }
}

希尔排序的优化实现

1. Knuth序列增量

希尔本人给出的增量序列为：d1=n/2, di=di-1/2 。但实际上这个增量序列并不是最优的，Knuth提出了一种增量序列：d1=1,di=3*di-1+1 。这个增量序列可以取到 O(n^1.25) 的时间复杂度。

我们可以将原始实现中的for循环修改一下即可：

public static void shellSort(int[] arr) {
    int n = arr.length;
    int gap = 1;
    while (gap < n / 3) {
        gap = gap * 3 + 1;
    }
    for (; gap > 0; gap /= 3) {
        for (int i = gap; i < n; i++) {
            for (int j = i; j >= gap && arr[j - gap] > arr[j]; j -= gap) {
                // 交换位置
                int temp = arr[j];
                arr[j] = arr[j - gap];
                arr[j - gap] = temp;
            }
         }
    }
}

2. 使用插入排序

希尔排序可以看作是插入排序的一种优化版，我们可以在内层循环中使用插入排序，并且使用直接插入排序的优化，这样可以进一步提升排序效率。示例代码如下：

public static void shellSort(int[] arr) {
    int n = arr.length;
    int gap = 1;
    while (gap < n / 3) {
        gap = gap * 3 + 1;
    }
    for (; gap > 0; gap /= 3) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
    }
}

示例说明

示例1

假设有一个数组arr，其值为{3, 7, 2, 1, 9, 5, 8, 4}。我们对其进行希尔排序，使用增量序列d1=1, di=3*di-1+1。

1. gap=4，将整个序列分成了4组：3 9、7 5、2 8、1 4，对每一组进行插入排序，得到{3, 5, 2, 1, 9, 7, 8, 4}；
2. gap=1，将整个序列分成了1组：3 5 2 1 9 7 8 4，对整个序列进行插入排序，得到{1, 2, 3, 4, 5, 7, 8, 9}。

最终的排序结果为{1, 2, 3, 4, 5, 7, 8, 9}。

示例2

假设有一个数组arr，其值为{9, 1, 5, 8, 3, 7, 4, 6, 2}。我们对其进行希尔排序，使用增量序列d1=4，d2=2，d3=1。

1. gap=4，将整个序列分成了两组：9 3 4 2 与 1 5 7 6 8，对每一组进行插入排序，得到{2, 3, 4, 6, 1, 5, 7, 9, 8}；
2. gap=2，将整个序列分成了两组：2 4 1 7 8 与 3 6 5 9，对每一组进行插入排序，得到{1, 2, 4, 5, 3, 6, 7, 9, 8}；
3. gap=1，整个序列为{1, 2, 4, 5, 3, 6, 7, 9, 8}，对其进行插入排序，得到{1, 2, 3, 4, 5, 6, 7, 8, 9}。

最终的排序结果为{1, 2, 3, 4, 5, 6, 7, 8, 9}。