排序算法 Hill sort：java、Kotlin、python 代码实现

terry 2年前 (2023-09-27) 阅读数 63 #数据结构与算法

Hill sort

核心：基于插入排序，对数组中任意区间 h 的元素进行排序，即每个元素被分为 h 份范围使用插入排序。该实现可能类似于插入排序，但可以在不同的步骤中使用。它更高效的原因是它考虑了子数组的大小和顺序。

山排序基于插入排序的以下两个性质提出了一种改进方法：

插入排序用于对几乎已经排好序的项进行排序。。操作数据时，效率高，即有线性排序的效率
但插入排序通常效率较低，因为插入排序一次只能移动数据一位

算法实现

通过将所有比较元素更多地划分为区域来提高插入排序的性能。这允许一个元素一次向其最终位置迈出一大步。然后算法以越来越小的步长对其进行排序。算法的最后一步是普通的插入排序，不过这一步待排序的数据已经排好序了（此时插入比较快）

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

然后插入4组的排列。排序结果为：

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

然后插入2组的排序顺序。，排序结果为：

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

图片来自于常见的排序算法——希尔排序（希尔排序）

步骤顺序

选择步长是选山的重要一环。只要最后一步为 1，任何步骤序列都有效。该算法首先以特定步长进行排序。然后以一定的步长继续排序，最终算法以步数为 1 进行排序。如果步长为1，则算法切换到插入排序，这保证了数据是有序的。

性能更好的下一个步骤序列

Shell 的原始序列：N/2 , N/4 , ..., 1（重复除以 2）；
Hibbard 的步骤：1, 3, 7 , . .., 2k - 1 ;
Knuth 步数：1, 4, 13, ..., (3k - 1) / 2 ； . 5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …

建议了最佳的走法顺序作者：塞奇威克 (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))
复制代码