Shell Sort(希爾排序法)
介紹
希爾排序法（Shell Sort）是 Donald Shell 於 1959 年提出的一種排序演算法，是插入排序法（Insertion Sort）的一種改良版本
shell sort 沒有規定要用哪種 gap 公式，不同的公式，其時間複雜度也不同。因此 shell sort 是一種不穩定的排序演算法。在 Shell 的原稿中，他建議初始的間距為 ，簡單地把每一次排序分成兩半。因此對於一個 n=100 的陣列，逐漸減少的間距序列會是：50, 25, 12, 6, 3, 1。具體實作如下：
學習資源
範例程式碼
javascript
function shellSort2(array) {
// shell sequence [1, 2, 4, 9, 19, 39, 78, 156, 312, 625, 1250, 2500, 5000]
const n = array.length;
const gaps = [];
let gap = n;
while (gap != 1) {
gap = Math.floor(gap / 2);
gaps.unshift(gap);
}
while ((gap = gaps.pop())) {
// 對每個子陣列進行 insertion sort
}
}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]Contributors
lucashsu95