[Java算法系列教程]-希尔排序

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

举例说明

这个算法无论怎么解释都会显得含糊不清，直接来个栗子。

假设现在有一数组 arr：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]，我们设定初始化步长为 gap = arr.length/2 = 10/2，即 5。按照我们上面说的「跳跃分割策略」，按增量为 5 分割子数组，将每列看成是一个子数组：

// 列1 列2 列3 列4 列5
   8   9   1   7   2
   3   5   4   6   0

然后对每列进行类直接插入排序，可得：

// 列1 列2 列3 列4 列5
   3   5   1   6   0
   8   9   4   7   2

则此时原数组顺序应变成：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]，然后再缩小增量，gap = 5/2 = 2，则数组分割如下：

// 列1 列2
   3   5
   1   6
   0   8
   9   4
   7   2

继续对每列进行直接插入排序，可得：

// 列1 列2
   0   2
   1   4
   3   5
   7   6
   9   8

则此时元素组顺序应变成：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]，这就是基本有序了。最后一轮再进行微调即可，所以此时增量应计算得为：gap = 2/2 = 1，则直接对数组应用直接插入排序即可，最后得到：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

代码示例

java

public static void shellSort(int[] array) {
    int number = array.length / 2;
    int i;
    int j;
    int temp;
    while (number >= 1) {
        for (i = number; i < array.length; i++) {
            temp = array[i];
            j = i - number;
            //需要注意的是，这里array[j] < temp将会使数组从小到大排序。
            while (j >= 0 && array[j] < temp) {
                array[j + number] = array[j];
                j = j - number;
            }
            array[j + number] = temp;
        }
        number = number / 2;
    }
}

python

def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = gap // 2
    return list