# 希爾排序 (Shell sort)

## 簡介
希爾排序（Shellsort），也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。

謝爾排序法是**不穩定排序法**。

是基於插入排序的以下兩點性質而提出改進方法的：
* 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序O(n)的效率
* 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

## 思路
1. 步長設為陣列長度除以2，且每輪步長都會再除以2，直至以1為步長進行排序。
2. 以步長分割的每組數之間進行直接插入排序。
3. 當以1步長進行排序時即為簡單插入排序。

## 算法
1. 先計算出陣列長度
2. 使用陣列長度計算出 gap
3. 用 gap 來跨越比較數值大小，進行插入排序

## 時間複雜度
假設今天要對一陣列使用希爾排序法由小到大排序。

### 最佳：O(n)

### 平均：O(n^2^) ~ O(n^1.5^)
依選用的步長而定。
### 最差：O(n^5/4^)

## 參考資料
- [ithome](https://ithelp.ithome.com.tw/articles/10277847)