以下範例一律以 var a = [4,2,6,3,1,9,5,7,8,0] 為輸入,方便對照每一輪的中間狀態。
希爾排序是插入排序的改良版。插入排序每次只跟相鄰的元素比較,資料稍微大她一點就得一格一格往后挪;希爾排序的做法是先跳著比——用一個 gap 把陣列切成若干子序列,各自做插入排序,然後逐步縮小 gap,最後以 gap=1 收尾。這樣一來,元素在早期的「粗調」階段就能長距離移動,最後一輪的插入排序幾乎不用怎麼搬。
function shellsort(arr) {
var i, k, j, len = arr.length,
gap = Math.ceil(len / 2), temp;
while (gap > 0) {
for (k = 0; k < gap; k++) {
// 對間隔為 gap 的子序列做插入排序
for (i = k + gap; i < len; i = i + gap) {
temp = arr[i];
for (j = i - gap; j > -1; j = j - gap) {
if (arr[j] > temp) {
arr[j + gap] = arr[j]; // 往後挪
} else {
break;
}
}
arr[j + gap] = temp; // 插入
}
}
gap = parseInt(gap / 2); // 縮小間隔
}
return arr;
}
執行過程(節錄):
gap = 5: [4,9] [2,5] [6,7] [3,8] [1,0] 五組各自排序
→ [4,2,6,3,0,9,5,7,8,1]
gap = 2: [4,6,0,5,8] 與 [2,3,9,7,1] 兩組排序
→ [0,1,4,2,5,3,6,7,8,9]
gap = 1: 一般插入排序收尾
→ [0,1,2,3,4,5,6,7,8,9]
可以明顯看到 gap=5 那輪,索引 0 和 5(4 與 9)、1 和 6(2 與 5)……各自成組比較。等到 gap=1 的最後一輪,陣列已經大致有序,插入排序要搬的次數非常少——這正是希爾排序比樸素插入排序快的原因。
分治法(divide and conquer)的代表。任選一個基準值(pivot),把數組分成「比它小」和「比它大」兩堆,然後對這兩堆分別遞迴同樣的動作,直到每堆只剩一個元素。通常以第一個元素當基準。
function quickSort(arr) {
var len = arr.length, leftArr = [], rightArr = [], tag;
if (len < 2) { return arr; } // 遞迴終止條件
tag = arr[0];
for (var i = 1; i < len; i++) {
if (arr[i] <= tag) {
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag, quickSort(rightArr));
}
這個寫法簡潔好懂,但它不是原地排序——每次都建立新陣列,額外使用了 O(n) 的空間。實務上的快速排序會用雙指標在原陣列內做分割(partition),空間才能壓到 O(log n)。另外,「固定取第一個元素當 pivot」在遇到已排序或接近已排序的資料時會退化成 O(n²),實作時通常改成隨機取或三數取中。
思路是「先合併兩個已排序的序列」。做法從最小的單位(單一元素)開始,兩兩合併成有序的小段,再把这些有序小段继续两两合併,最後整組就有序了。
function subSort(arr1, arr2) {
var bArr1 = arr1.slice(), bArr2 = arr2.slice(), arr3 = [];
// 兩邊都還有元素時,每次取較小的那個
while (bArr1.length != 0 || bArr2.length != 0) {
if (bArr1.length == 0) {
arr3 = arr3.concat(bArr2);
bArr2.length = 0;
} else if (bArr2.length == 0) {
arr3 = arr3.concat(bArr1);
bArr1.length = 0;
} else {
if (bArr1[0] <= bArr2[0]) {
arr3.push(bArr1[0]);
bArr1.shift();
} else {
arr3.push(bArr2[0]);
bArr2.shift();
}
}
}
return arr3;
}
注意它預設輸入的兩個陣列已經各自有序,這正是歸並排序能達到 O(n log n) 的關鍵——合併兩個有序序列本身是線性的。
function mergeSort(arr) {
var len = arr.length, arrleft = [], arrright = [],
gap = 1, maxgap = len - 1, gapArr = [], glen, n;
// 先算出會用到的所有 gap:1, 2, 4, 8 ...
while (gap < maxgap) {
gap = Math.pow(2, n);
if (gap <= maxgap) { gapArr.push(gap); }
n++;
}
glen = gapArr.length;
for (var i = 0; i < glen; i++) {
gap = gapArr[i];
for (var j = 0; j < len; j = j + gap * 2) {
arrleft = arr.slice(j, j + gap);
arrright = arr.slice(j + gap, j + gap * 2);
arr = arr.slice(0, j).concat(subSort(arrleft, arrright), arr.slice(j + gap * 2));
}
}
return arr;
}
執行過程:
第一輪 gap=1:合併 [4,2] [6,3] [1,9] [5,7] [8,0]
→ [2,4,3,6,1,9,5,7,0,8]
第二輪 gap=2:合併 [2,4]+[3,6] [1,9]+[5,7] [0,8]+[]
→ [2,3,4,6,1,5,7,9,0,8]
第三輪 gap=4:合併 [2,3,4,6]+[1,5,7,9] [0,8]+[]
→ [1,2,3,4,5,6,7,9,0,8]
第四輪 gap=8:合併 [1,2,3,4,5,6,7,9]+[0,8]
→ [0,1,2,3,4,5,6,7,8,9]
可以清楚看到合併單位依序是 1 → 2 → 4 → 8,每輪把相鄰的兩個有序段拼成一個更大的有序段。
快速排序在一般情況下是平均表現最好的,因為常數因子小、快取友善;缺點是穩定性差、最壞情況 O(n²)。
歸並排序時間穩定保證 O(n log n),而且是穩定排序(相等元素的相對順序不變),因此適合排序物件或需要保留原順序的場景;代價是需要 O(n) 的額外空間。外部排序(資料大到記憶體放不下)也只能用它。
希爾排序是插入排序的改良,實作簡單、原地排序、空間 O(1),在中等規模或記憶體受限的環境下有它的位置,但一般用途已多半被前兩者取代。
實務上一個常見的折衷是混合排序:大陣列用快速排序遞迴分割,當子陣列小到某個門檻(例如 16 個元素)就切成插入排序——因為小陣列下插入排序的常數反而更小。多數標準函式庫都是這樣做的。
最後提醒:以上範例為教學目的而寫,重在展示每一輪的中間狀態。真正在專案裡排序,請直接用 Array.prototype.sort(),它已經過高度優化。