希爾排序法(Shell Sort)是插入排序(Insertion Sort)的改良版。可減少插入排序的資料搬移次數，加入了間距(Gap)的概念將資料分成多個小區塊，再將不同區塊資料進行插入排序，每一回合Gap會漸漸減少，最後一回Gap會是1。

操作流程:

• 由大到小制定數個間距(Gap)，最後一次的Gap一定要是1
• 將資料依制定的間距(Gap)分組
• 每組進行插入排序
• 重複上述步驟，不斷減少Gap，直到最後一次Gap是1完成為止。

間距(Gap)的選擇:

發明人D.L Shell原先的Gap選擇為:N/2、N/4、...1(反覆除以2)

間距Gap的選擇有非常多種，這邊用最初發明人為例，其他選擇可自行google研究。

下面利用60 80 20 30 40 70 50 10由小到大排序。

時間複雜度會因選用的GAP有所不同，但因為是插入排序改良版，幾乎所有狀況都能比O(n²)來得快。

插入排序法的介紹可以參考此篇。

JavaScript

let data = [8, 6, 10, 5, 3, 9, 2, 7, 4, 1]

function ShellSort(data) {
  let i, j, tmp;
  let gap = parseInt(data.length / 2);
  
  for (gap; gap > 0; gap = parseInt(gap / 2)) {
    //開始插入排序法 
    for (i = gap; i < data.length; i++) {
      tmp = data[i];
      for (j = i; j >= gap && tmp < data[j - gap]; j -= gap) {
        data[j] = data[j - gap];
      }
      data[j] = tmp;
    }
  }
  return data
}

console.log(ShellSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Shell Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def ShellSort(data):
    n = len(data)
    gap = n // 2 
    while gap > 0: 
        for i in range(gap,n): 
            temp = data[i] 
            j = i 
            while  j >= gap and data[j-gap] > temp: 
                data[j] = data[j-gap] 
                j = j - gap 
            data[j] = temp 
        gap = gap // 2
    return data
        
print(ShellSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]