希爾排序

1. 前言

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

2. 什么是希爾排序？

希爾排序（Shell Sort），是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中較為簡單的一種排序算法。

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

3. 希爾排序過程

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

3.1 算法步驟

1. 步驟 1：

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

2. 步驟 2：

按照增量序列的個(gè)數(shù) m，對(duì)整個(gè)待排序序列進(jìn)行 m 趟排序。

3. 步驟 3：

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

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

3.2 算法演示

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

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

接著，我們調(diào)用 2.1 中的步驟 2, 步驟 3，按照增量值的取法，依次進(jìn)行對(duì)應(yīng)序列的插入排序，首先我們?nèi)≡隽恐禐?3，對(duì)應(yīng)排序示例如下：

[9,2,11,7,12,5]   -->  [9,7],[2,12],[11,5]	 //增量取3，整個(gè)待排序序列按照增量為3進(jìn)行分組，分成3組，依次排序
[9,7],[2,12],[11,5] -->  [7,9],[2,12],[5,11]   //對(duì)應(yīng)增量位置進(jìn)行排序
[7,9],[2,12],[5,11] -->  [7,2,5,9,12,11]   //完成第一次的對(duì)應(yīng)增量的排序過程

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

在完成增量為 3 的插入排序之后，我們接著進(jìn)行增量為 1 的插入排序，這個(gè)步驟其實(shí)跟我們之前的插入排序步驟完全一致。整個(gè)過程如下：

[7,2,5,9,12,11]     -->  [7];[2,5,9,12,11]	 //插入排序初始化，選擇第一個(gè)元素作為排序好的序列
[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 時(shí)候執(zhí)行 步驟 3，實(shí)際上就是執(zhí)行一次插入排序，只是在執(zhí)行插入排序之前，之前的序列在一定程度上面已經(jīng)進(jìn)行了插入排序，所以在增量為 1 的插入排序過程中可以減少插入時(shí)候比較的次數(shù)，從而可以在一定程度上面減少算法的運(yùn)行時(shí)間。

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

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

在說明希爾排序的整個(gè)過程之后，接下來，我們看看如何用 Java 代碼實(shí)現(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;
        //不斷地進(jìn)行插入排序，直至增量為1
        while (true) {
            //增量每次減半
            gap = gap/2;
            for (int i = 0; i < gap; i++) {
                //內(nèi)部循環(huán)是一個(gè)插入排序
                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之后，希爾排序結(jié)束，退出循環(huán)
            if (gap == 1)
                break;
        }
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

運(yùn)行結(jié)果如下：

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

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

5. 小結(jié)

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