插入排序在處理近乎已排序的資料時效率極高,可達到線性排序的水準;但它一般偏低效,因為每次只能把資料移動一個位置。希爾排序(Shell sort)正是針對這兩點提出的改良版本。
這個演算法以其設計者希爾(Donald Shell)命名,於 1959 年發表。部分舊版教科書稱之為 Shell-Metzner,但據 Metzner 本人說法,他並未參與其中,名字不應被冠上。

基本思想:先取一個小於 n 的整數 d1 作為第一個增量,把全部記錄分成 d1 組,將距離為 d1 倍數的記錄歸在同一組,先在各組內做直接插入排序;接著取第二個增量 d2 < d1 重複分組與排序,直到增量 dt=1,此時所有記錄歸在同一組做插入排序為止。本質上,它是一種分組插入的方法。
實例一:
function shellSort(list) {
var gap = Math.floor(list.length / 2);
while (gap > 0) {
for (i = gap; i < list.length; i++) {
temp = list[i];
for (j = i; j >= gap && list[j - gap] > temp; j -= gap) {
list[j] = list[j - gap];
}
list[j] = temp;
}
gap = Math.floor(gap / 2);
}
return list;
};
// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
shellSort(arr);
實例二:
<script type="text/javascript">
function shellSort(array) {
var j, i, v, h = 1, s = 3, k, n = array.length;
var result = "";
var count = 0;
while (h < n)
h = s * h + 1;
while (h > 1) {
h = (h - 1) / s;
for (k = 0; k < h; k++)
for (i = k + h, j = i; i < n; i += h, j = i) {
v = array[i];
while (true)
if ((j -= h) >= 0 && array[j] > v)
array[j + h] = array[j];
else
break;
array[j + h] = v;
}
count++;
result += "<br />第" + count + "遍排序的結果是:";
for (var n = 0; n < array.length; n++) {
result += array[n] + ",";
}
}
return result;
}
</script>