希尔排序

歷史

希爾排序按其設計者希爾（Donald Shell）的名字命名，該演算法由1959年公布。一些老版本教科書和參考手冊把該演算法命名為Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根據Metzner本人的說法，「我沒有為這種演算法做任何事，我的名字不應該出現在演算法的名字中。」

演算法實現

原始的演算法實現在最壞的情況下需要進行O(n²)的比較和交換。 V. Pratt的書對演算法進行了少量修改，可以使得效能提升至O(n log² n)。這比最好的比較演算法的O(n log n)要差一些。
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的效能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的資料幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的資料在一個已按升序排好序的數組的末端。如果用複雜度為O(n²)的排序（泡沫排序或插入排序），可能會進行n次的比較和交換才能將該資料移至正確位置。而希爾排序會用較大的步長移動資料，所以小資料只需進行少數比較和交換即可到正確位置。
一個更好理解的希爾排序實現：將數組列在一個表中並對列排序（用插入排序）。重複這過程，不過每次用更長的行來進行。最後整個表就只有一行了。將數組轉換至表是為了更好地理解這演算法，演算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++ ）。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5行的表中來更好地描述演算法，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然後我們對每行進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四列數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然後再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之後變為：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最後以1步長進行排序（此時就是簡單的插入排序了）。

虛擬碼

input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:    
    for i = inc .. n − 1 do:        
        temp ← a[i]        
        j ← i        
        while j ≥ inc and a[j − inc] > temp do:            
            a[j] ← a[j − inc]            
            j ← j − inc        
        a[j] ← temp    
    inc ← round(inc / 2)
輸入：1個長度為n的矩陣a，矩陣的編號從0到n - 1
整數inc從n / 2到1，每次循環inc變為inc / 2
i從inc到n - 1，每次循環i變為i + 1
將a[ i ]的值賦給temp
j從i 到inc，每次循環j變為j - inc
如果a[ j − inc ]大於temp，則將a[ j - inc ]的值賦給a[ j ]
否則跳出j循環
j循環结束
將temp的值賦给a[ j ]
i循環结束
inc循環结束

C語言

void shell_sort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}}

C++

template<typename T>void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }}

Java

public static void shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] < temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

JavaScript

Array.prototype.shell_sort = function() {
var gap, i, j;
var temp;
for (gap = this.length >> 1; gap > 0; gap >>= 1)
for (i = gap; i < this.length; i++) {
temp = this[i];
for (j = i - gap; j >= 0 && this[j] > temp; j -= gap)
this[j + gap] = this[j];
this[j + gap] = temp;
}return this};

Python

def shell_sort(list):
    n = len(list)
    # 初始步長
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步長進行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步長
        gap = gap // 2
    return list

PHP

function shell_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
for ($gap = count($arr)>>1; $gap > 0; $gap>>=1)
for ($i = $gap; $i < count($arr); $i++) {
$temp = $arr[$i];
for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap)
$arr[$j + $gap] = $arr[$j];
$arr[$j + $gap] = $temp;
}}

Go

package mainimport (
"fmt")func ShellSort(array []int) {
n := len(array)
if n < 2 {
return
}
key := n / 2
for key > 0 {
for i := key; i < n; i++ {
j := i
for j >= key && array[j] < array[j-key] {
array[j], array[j-key] = array[j-key], array[j]
j = j - key
}
}
key = key / 2
}}func main() {
array := []int{
55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,
}
fmt.Println(array)
ShellSort(array)
fmt.Println(array)}