关于程序员:什么是希尔排序

40次阅读

共计 2631 个字符，预计需要花费 7 分钟才能阅读完成。

本文首发自「慕课网」，想理解更多 IT 干货内容，程序员圈内热闻，欢送关注！

作者 | 慕课网精英讲师 JdreamZhang

希尔排序（Shell Sort），是计算机科学与技术畛域中较为简单的一种排序算法。

希尔排序是插入排序的一种，有时候也被称为“放大增量排序”。它是插入排序的改进版，与插入排序的不同之处在于，希尔排序会优先比拟间隔较远的元素。希尔排序是依照其设计者希尔（Donald Shell）的名字命名而来，并于 1959 年公布出来。

希尔排序过程
在介绍完希尔排序之后，咱们一起来看一下希尔排序的实现步骤具体是什么样的吧。这里咱们假如待排序的序列为 [9,2,11,7,12,5]，咱们依照从小到大的序列进行排序。

1.1 算法步骤
步骤 1：
抉择一个增量序列 k1，k2, … km，其中 k1>k2>…km=1，即增量序列大小顺次减小，并且最初一个增量序列大小为 1。

步骤 2：
依照增量序列的个数 m，对整个待排序序列进行 m 趟排序。

步骤 3：
每一趟排序，依据对应的增量 ki，须要将待排序的序列分成对应长度的子序列，别离在子序列下面进行间接插入排序。当且仅当增量序列为 1 时，整个序列作为一个整体解决。

其实，下面的步骤 1 和步骤 2 都是在排序之前进行的解决，抉择对应的增量。下面的步骤 3 每执行一次，就相当于是进行了一次插入排序，只是每次都会抉择一个增量，将整个待排序序列依照增量进行划分，而后在对应增量下面进行插入排序。接下来，让咱们用下面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

1.2 算法演示
依照 2.1 节的排序步骤，咱们须要先抉择对应的希尔排序中的增量值，依照一般性的准则，咱们能够将增量依照待排序的序列长度顺次整除 2，直到增量为 1 进行，失去对应的增量。如下：

6/2 = 3, 3/2 = 1 // 顺次取得增量值 3,1，除法取整
代码块 1
接着，咱们调用 2.1 中的步骤 2, 步骤 3，依照增量值的取法，顺次进行对应序列的插入排序，首先咱们取增量值为 3，对应排序示例如下：

[9,2,11,7,12,5] –> [9,7],[2,12],[11,5] // 增量取 3，整个待排序序列依照增量为 3 进行分组，分成 3 组，顺次排序
[9,7],[2,12],[11,5] –> [7,9],[2,12],[5,11] // 对应增量地位进行排序
[7,9],[2,12],[5,11] –> [7,2,5,9,12,11] // 实现第一次的对应增量的排序过程
代码块 123
Tips: 希尔排序过程中会每次抉择一个增量值，而后将待排序列表依照增量值进行分组，对应的分组外部进行插入排序。

在实现增量为 3 的插入排序之后，咱们接着进行增量为 1 的插入排序，这个步骤其实跟咱们之前的插入排序步骤完全一致。整个过程如下：

[7,2,5,9,12,11] –> [7];[2,5,9,12,11] // 插入排序初始化，抉择第一个元素作为排序好的序列
[7];[2,5,9,12,11] –> [2,7];[5,9,12,11] // 抉择未排序元素 2，插入排序好的序列[7] 造成新的排序好序列 [2,7]
[2,7];[5,9,12,11] –> [2,5,7];[9,12,11] // 抉择未排序元素 5，插入排序好的序列[2,7] 造成新的排序好序列 [2,5,7]
[2,5,7];[9,12,11] –> [2,5,7,9];[12,11] // 抉择未排序元素 9，插入排序好的序列[2,5,7] 造成新的排序好序列 [2,5,7,9]
[2,5,7,9];[12,11] –> [2,5,7,9,12];[11] // 抉择未排序元素 12，插入排序好的序列[2,5,7,9] 造成新的排序好序列 [2,5,7,9,12]
[2,5,7,9,12];[11] –> [2,5,7,9,11,12] // 抉择未排序元素 11，插入排序好的序列[2,5,7,9,12] 造成新的排序好序列 [2,5,7,9,11,12]
代码块 123456
Tips: 增量为 1 时候执行步骤 3，实际上就是执行一次插入排序，只是在执行插入排序之前，之前的序列在肯定水平下面曾经进行了插入排序，所以在增量为 1 的插入排序过程中能够缩小插入时候比拟的次数，从而能够在肯定水平下面缩小算法的运行工夫。

从下面的示例能够看出，其实整个希尔排序的过程，就是依据增量大小顺次进行插入排序，实质上还是针对插入排序的一种优化。

Java 代码实现
在阐明希尔排序的整个过程之后，接下来，咱们看看如何用 Java 代码实现希尔排序算法。

import java.util.Arrays;

public class ShellSort {

public static void main(String[] args) {

    // 初始化须要排序的数组
    int array[] = {9, 2, 11, 7, 12, 5};
    // 初始化希尔排序的增量为数组长度
    int gap = array.length;
    // 一直地进行插入排序，直至增量为 1
    while (true) {
        // 增量每次减半
        gap = gap/2;
        for (int i = 0; i < gap; i++) {
            // 外部循环是一个插入排序
            for (int j = i + gap; j < array.length; j += gap) {int temp = array[j];
                int k = j - gap;
                while (k >= 0 && array[k] > temp) {array[k + gap] = array[k];
                    k -= gap;
                }
                array[k + gap] = temp;
            }
        }
        // 增量为 1 之后，希尔排序完结，退出循环
        if (gap == 1)
            break;
    }
    // 打印出排序好的序列
    System.out.println(Arrays.toString(array));
}

}
代码块 1234567891011121314151617181920212223242526272829303132333435
运行后果如下：

[2, 5, 7, 9, 11, 12]
代码块 1
代码中的第 8 行初始化一个须要排序的数组，前面依照从小到大的排序规定，实现了数组的排序。第 12 行至 30 行是整个希尔排序的流程。第 14 行代码示意希尔排序中的增量每次整除 2 获得，第 17 行至 25 行是一个 for 循环构造，表明依照增量进行插入排序。最初第 32 行代码输入排序好的数组。