【Day24】[演算法]-希尔排序法Shell Sort

希尔排序法(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]