十大经典排序算法-希尔排序

排序算法

编程算法

发布日期: 2020-10-20

文章字数: 966

阅读时长: 3 分

前言

本文重点讲解十大经典排序算法的希尔排序

要点

希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本，该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:

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

基本思想

该方法实质上是一种分组插入方法。
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

代码实现

以下代码由java实现

public class ShellSort {

    /**
     * 希尔排序
     * @param arr
     * @param n
     * @return
     */
    public static int[] sort(int[] arr, int n) {
        if (n <= 0) {
            return null;
        }
        // 初始化参数
        int key, i, j;
        // 初始增量 inc , 每趟过后 inc 除以 2
        for (int inc = n / 2; inc > 0; inc = inc / 2) {
            // 每一趟采用插入排序
            for (i = inc; i < n; i++) {
                // 保存当前key
                key = arr[i];
                // 当前key要比上一个元素小才交换
                for (j = i; j >= inc && key < arr[j - inc]; j -= inc) {
                    arr[j] = arr[j - inc];
                }
                // 注意 j -= inc
                arr[j] = key;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23};
		System.out.println(Arrays.toString(sort(arr, arr.length)));
    }
}

时间性能

增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：

最后一个增量必须为1；
应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在$n^1.25$到$(1.6n)^1.25$之间。

Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：

当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度$O(n)$和最坏时间复杂度$0(n^2)$差别不大。
在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。