希爾排序

1. 前言

本節(jié)內(nèi)容是排序算法系列之一：希爾排序，主要講解了希爾排序的主體思路，選取了一個待排序的數(shù)字列表對希爾排序算法進行了演示，給出了希爾排序算法的 Java 代碼實現(xiàn)，幫助大家可以更好的理解希爾排序算法。

2. 什么是希爾排序？

希爾排序（Shell Sort），是計算機科學與技術領域中較為簡單的一種排序算法。

希爾排序是插入排序的一種，有時候也被稱為 “縮小增量排序”。它是插入排序的改進版，與插入排序的不同之處在于，希爾排序會優(yōu)先比較距離較遠的元素。希爾排序是按照其設計者希爾（Donald Shell）的名字命名而來，并于 1959 年公布出來。

3. 希爾排序過程

在介紹完希爾排序之后，我們一起來看一下希爾排序的實現(xiàn)步驟具體是什么樣的吧。這里我們假設待排序的序列為 [9,2,11,7,12,5]，我們按照從小到大的序列進行排序。

3.1 算法步驟

1. 步驟 1：

選擇一個增量序列 k1，k2, … km，其中 k1>k2>…km=1，即增量序列大小依次減小，并且最后一個增量序列大小為 1。

2. 步驟 2：

按照增量序列的個數(shù) m，對整個待排序序列進行 m 趟排序。

3. 步驟 3：

每一趟排序，根據(jù)對應的增量 ki，需要將待排序的序列分成對應長度的子序列，分別在子序列上面進行直接插入排序。當且僅當增量序列為 1 時，整個序列作為一個整體處理。

其實，上面的步驟 1 和 步驟 2 都是在排序之前進行的處理，選擇對應的增量。上面的 步驟 3 每執(zhí)行一次，就相當于是進行了一次插入排序，只是每次都會選擇一個增量，將整個待排序序列按照增量進行劃分，然后在對應增量上面進行插入排序。接下來，讓我們用上面的待排序數(shù)字隊列 [9,2,11,7,12,5] 進行整個算法步驟的排序演示工作。

3.2 算法演示

按照 2.1 節(jié)的排序步驟，我們需要先選擇對應的希爾排序中的增量值，按照一般性的原則，我們可以將增量按照待排序的序列長度依次整除 2，直到增量為 1 停止，得到對應的增量。如下：

6/2 = 3, 3/2 = 1    //依次獲得增量值3,1，除法取整

接著，我們調(diào)用 2.1 中的步驟 2, 步驟 3，按照增量值的取法，依次進行對應序列的插入排序，首先我們?nèi)≡隽恐禐?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]   //完成第一次的對應增量的排序過程

Tips: 希爾排序過程中會每次選擇一個增量值，然后將待排序列表按照增量值進行分組，對應的分組內(nèi)部進行插入排序。

在完成增量為 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]

Tips: 增量為 1 時候執(zhí)行 步驟 3，實際上就是執(zhí)行一次插入排序，只是在執(zhí)行插入排序之前，之前的序列在一定程度上面已經(jīng)進行了插入排序，所以在增量為 1 的插入排序過程中可以減少插入時候比較的次數(shù)，從而可以在一定程度上面減少算法的運行時間。

從上面的示例可以看出，其實整個希爾排序的過程，就是根據(jù)增量大小依次進行插入排序，本質(zhì)上還是針對插入排序的一種優(yōu)化。

4. Java 代碼實現(xiàn)

在說明希爾排序的整個過程之后，接下來，我們看看如何用 Java 代碼實現(xiàn)希爾排序算法。

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {

        //初始化需要排序的數(shù)組
        int array[] = {9, 2, 11, 7, 12, 5};
        //初始化希爾排序的增量為數(shù)組長度
        int gap = array.length;
        //不斷地進行插入排序，直至增量為1
        while (true) {
            //增量每次減半
            gap = gap/2;
            for (int i = 0; i < gap; i++) {
                //內(nèi)部循環(huán)是一個插入排序
                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之后，希爾排序結束，退出循環(huán)
            if (gap == 1)
                break;
        }
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

運行結果如下：

[2, 5, 7, 9, 11, 12]

代碼中的第 8 行初始化一個需要排序的數(shù)組，后面按照從小到大的排序規(guī)則，實現(xiàn)了數(shù)組的排序。第 12 行至 30 行是整個希爾排序的流程。第 14 行代碼表示希爾排序中的增量每次整除 2 取得，第 17 行至 25 行是一個 for 循環(huán)結構，表明按照增量進行插入排序。最后第 32 行代碼輸出排序好的數(shù)組。

5. 小結

本節(jié)主要學習了希爾排序算法，通過本節(jié)課程的學習，需要熟悉希爾排序的算法流程，知道希爾排序算法的實現(xiàn)思路，可以自己用代碼實現(xiàn)希爾排序算法。至此，我們已經(jīng)學習了排序算法中的冒泡排序、插入排序、選擇排序、希爾排序。