（6）希爾排序 (Shell Sort)

算法原理

希爾排序算法是按其設(shè)計(jì)者希爾（Donald Shell）的名字命名，該算法由1959年公布，是插入排序的一種更高效的改進(jìn)版本。它的作法不是每次一個(gè)元素挨一個(gè)元素的比較。而是初期選用大跨步（增量較大）間隔比較，使記錄跳躍式接近它的排序位置；然后增量縮?。蛔詈笤隽繛?1 ，這樣記錄移動次數(shù)大大減少，提高了排序效率。希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴(yán)格規(guī)定。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率
• 但插入排序一般來說是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位

算法思路：

1. 先取一個(gè)正整數(shù) d1(d1?1?個(gè)組，所有距離為 d1?的倍數(shù)的記錄看成一組，然后在各組內(nèi)進(jìn)行插入排序
2. 然后取 d2(d2?1)
3. 重復(fù)上述分組和排序操作；直到取 di?= 1(i >= 1) 位置，即所有記錄成為一個(gè)組，最后對這個(gè)組進(jìn)行插入排序。一般選 d1?約為 n/2，d2?為 d1?/2， d3?為 d2/2 ，…， di?= 1。

圖片來自維基百科

實(shí)例分析

假設(shè)有數(shù)組 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1?= 4，將數(shù)組分為 4 組，如下圖中相同顏色代表一組：

然后分別對 4 個(gè)小組進(jìn)行插入排序，排序后的結(jié)果為：

然后，取 d2?= 2，將原數(shù)組分為 2 小組，如下圖：

然后分別對 2 個(gè)小組進(jìn)行插入排序，排序后的結(jié)果為：

最后，取 d3?= 1，進(jìn)行插入排序后得到最終結(jié)果：

JavaScript 語言實(shí)現(xiàn)

按照慣例，下面給出了 JavaScript 的算法實(shí)現(xiàn)：

function shellSort(array) {

    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }

    var length = array.length,
        gap = Math.floor(length / 2);

    while (gap > 0) {
        for (var i = gap; i < length; i++) {
            for (var j = i; 0 < j; j -= gap) {
                if (array[j - gap] > array[j]) {
                    swap(array, j - gap, j);
                } else {
                    break;
                }
            }
        }

        gap = Math.floor(gap / 2);
    }

    return array;
}

參考文章

• 維基百科，自由的百科全書
• 希爾排序基本思想
• [演算法] 希爾排序法(Shell Sort)
• 算法系列15天速成——第三天 七大經(jīng)典排序【下】
• Algorithm Implementation/Sorting/Shell sort