希尔排序算法

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

历史

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”

动图演示

以23, 10, 4, 1的步长序列进行希尔排序

数据结构 : 数组
最坏时间复杂度 : 根据步长序列的不同而不同。已知最好的：O(nlog²n)
最优时间复杂度 : O(n)
平均时间复杂度 : 根据步长序列的不同而不同。
最坏空间复杂度 : O(n)

算法实现

原始的算法实现在最坏的情况下需要进行 O(n2) 的比较和交换。 V. Pratt的书[1]对算法进行了少量修改，可以使得性能提升至 O(n log²n)。这比最好的比较算法的 O(n log n) 要差一些。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为 O(n2) 的排序（冒泡排序或插入排序），可能会进行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为步长进行排序：

排序之后变为：

最后以 1 步长进行排序（此时就是简单的插入排序了）。

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为 1 任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为普通插入排序，这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为

并且对步长取半直到步长达到 1 。虽然这样取可以比

类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。

步长序列	最坏情况下复杂度
	$mathcal {O}}(n^{2}$
	$(n^{3/2})}(n^{3/2}$
	$n\log^2 n$

已知的最好步长序列是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该序列的项来自

和

这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是（斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列）：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

伪代码

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 >= 0 and j-gap >= 0 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 main

import (
  "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)

}