排序算法之希尔排序：java、Kotlin、python代码实现

菜小编

2018-9-10

数据结构与算法

希尔排序

核心：基于插入排序，使数组中任意间隔为 h 的元素都是有序的，即将全部元素分为 h 个区域使用插入排序。其实现可类似于插入排序但使用不同增量。更高效的原因是它权衡了子数组的规模和有序性

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

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

算法实现

通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）

假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，将数组分为 4 组，如下图中相同颜色代表一组：

然后分别对 4 个小组进行插入排序，排序后的结果为：

然后，取 d2 = 2，将原数组分为 2 小组，如下图：

然后分别对 2 个小组进行插入排序，排序后的结果为：

最后，取 d3 = 1，进行插入排序后得到最终结果：

图片摘自常见排序算法 - 希尔排序 (Shell Sort)

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

以下是性能比较好的步长序列

Shell's original sequence: N/2 , N/4 , ..., 1 (repeatedly divide by 2);
Hibbard's increments: 1, 3, 7, ..., 2k - 1 ;
Knuth's increments: 1, 4, 13, ..., (3k - 1) / 2 ;
Sedgewick's increments: 1, 5, 19, 41, 109, ....
It is obtained by interleaving the elements of two sequences:
1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…
5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)。这项研究也表明比较在希尔排序中是最主要的操作，而不是交换。用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

实现

Java

public class ShellSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        shellSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(" " + number);
        }

    }

    private static void shellSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;

        int gap = length / 2;
        int i, j;

        for (; gap > 0; gap /= 2) { // Shell's original sequence: N/2 , N/4 , ..., 1 (repeatedly divide by 2)
            for (i = gap; i < length; i += gap) {

                int temp = array[i];
                for (j = i; j > 0 && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }

                array[j] = temp;
            }
        }
    }
}
复制代码

Kotlin

object ShellSortKt {

    fun shellSort(array: IntArray) {

        if (array.isEmpty()) {
            return
        }

        val size = array.size
        var gap = size / 2

        while (gap > 0) {

            for (i in gap until size step gap) {

                val temp = array[i]
                var j = i

                while (j > 0 && array[j - gap] > temp) {
                    array[j] = array[j - gap]
                    j -= gap
                }

                array[j] = temp
            }

            gap /= 2
        }
    }
}

fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6, 5, 3, 1, 8, 7, 2, 4)
    ShellSortKt.shellSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")
    }
}
复制代码

Python3

#!/usr/bin/env python
# coding=utf-8


def shell_sort(arrayList):
    length = len(arrayList)

    gap = length // 2
    while (gap > 0):

        for i in range(gap, length, gap):
            holder = arrayList[i]
            j = i
            while (j > 0 and arrayList[j - gap] > holder):
                arrayList[j] = arrayList[j - gap]
                j -= gap

            arrayList[j] = holder

        gap //= 2


if __name__ == "__main__":
    arrayList = [6, 5, 3, 1, 8, 7, 2, 4]
    print("orgin array list: {0}".format(arrayList))
    shell_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
复制代码