筆試與面試經常涉及各種排序演算法。本文整理九種常見做法,逐一說明原理、實作步驟,並附上 JavaScript 程式碼與時間複雜度分析。
原理:插入排序簡單直觀,做法是「維護一個已排序序列」:對未排序的資料從後向前掃描已排序區,找到位置後插入。實作上通常采用 in-place 排序(額外空間 O(1)),因此掃描過程需要反覆把已排序元素往後挪,為新元素騰出插入空間。
步驟:
1. 從第一個元素開始,視為已排序;
2. 取出下一個元素,在已排序序列中從後向前掃描;
3. 若已排序元素大於新元素,就往後移一格;
4. 重複步驟 3,直到找到不大於新元素的位置;
5. 把新元素插入該位置;
6. 重複步驟 2~5。
function insertionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
for (var i = 1; i < array.length; i++) {
var key = array[i];
var j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
} else {
return 'array is not an Array!';
}
}
複雜度:最佳 O(n)(輸入已排序)、最壞 O(n²)(輸入反向排序)、平均 O(n²)。
原理:在直接插入排序上做的小改動。最大差別在於「尋找插入位置」時改用二分搜尋,比較次數得以降低。
步驟:
1. 從第一個元素開始,視為已排序;
2. 取出下一個元素,在已排序區用二分搜尋找出第一個比它大的位置;
3. 插入該位置;
4. 重複上述兩步。
function binaryInsertionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
for (var i = 1; i < array.length; i++) {
var key = array[i], left = 0, right = i - 1;
while (left <= right) {
var middle = parseInt((left + right) / 2);
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
for (var j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = key;
}
return array;
} else {
return 'array is not an Array!';
}
}
複雜度:最佳 O(n log n)、最壞與平均 O(n²)。搬移元素的成本仍在,所以整體量級沒有改變。
原理:在未排序區中找到最小(或最大)元素,放到已排序區的起始位置,接著從剩餘元素中再找最小者放到已排序區末尾,直到全部排完。
步驟:初始時有序區為空、無序區為 R[1..n];第 i 趟從無序區中挑出關鍵字最小的記錄 R[k],與無序區第一個記錄交換,使有序區加一、無序區減一;n-1 趟後陣列即完成排序。
function selectionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
var len = array.length, temp;
for (var i = 0; i < len - 1; i++) {
var min = array[i];
for (var j = i + 1; j < len; j++) {
if (array[j] < min) {
temp = min;
min = array[j];
array[j] = temp;
}
}
array[i] = min;
}
return array;
} else {
return 'array is not an Array!';
}
}
複雜度:最佳、最壞、平均皆為 O(n²),交換次數較少是它的特點。
原理:重複走訪要排序的序列,每次比較相鄰兩個元素,順序錯誤就交換。反覆進行直到沒有需要交換為止。名稱來自「越小的元素會經由交換慢慢浮到序列頂端」。
步驟:
1. 比較相鄰元素,若前者大於後者則交換;
2. 對每一對相鄰元素做同樣的事,走到最後一對時,最大值會落在尾端;
3. 對所有元素重複以上步驟,但每次少比較一個(已排好的尾端);
4. 重複直到排序完成。
function bubbleSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
var len = array.length, temp;
for (var i = 0; i < len - 1; i++) {
for (var j = len - 1; j >= i; j--) {
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
return array;
} else {
return 'array is not an Array!';
}
}
複雜度:最佳 O(n)(可搭配「本趟是否發生交換」的旗標提前結束)、最壞與平均 O(n²)。
原理:透過一趟排序把待排記錄切成兩半,一邊的關鍵字全部小於另一邊,再分別對兩邊遞迴排序。
步驟:
1. 從序列中挑出一個元素作為基準(pivot);
2. 重新排序:比基準小的放前面、大的放後面(相等者放任一邊),此操作稱為 partition,執行後基準位於最終位置;
3. 遞迴地對左右兩個子序列重複排序。
// 方法一:原地版本
function quickSort(array, left, right) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array'
&& typeof left === 'number' && typeof right === 'number') {
if (left < right) {
var x = array[right], i = left - 1, temp;
for (var j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
} else {
return 'array is not an Array or left or right is not a number!';
}
}
var aaa = [3, 5, 2, 9, 1];
quickSort(aaa, 0, aaa.length - 1);
console.log(aaa);
// 方法二:較易讀的版本
var quickSort2 = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort2(left).concat([pivot], quickSort2(right));
};
複雜度:最佳與平均 O(n log n)、最壞 O(n²)(例如已排序且基準挑得最差時)。方法二雖然好懂,但會額外配置陣列,空間成本較高。
原理:利用堆這種資料結構設計的排序。堆是近似完全二叉樹,並滿足堆的性質:子節點的鍵值總是小於(或大於)父節點。
步驟:
1. 把初始序列建成大頂堆,此即初始無序區;
2. 把堆頂 R[1] 與最後一個元素 R[n] 交換,得到新的無序區與有序區,且滿足 R[1..n-1] ≤ R[n];
3. 由於交換後堆頂可能違反堆性質,需將無序區重新調整為堆,再重複交換,直到有序區元素數為 n-1。
/* 堆排序 @param array 待排序陣列 */
function heapSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
var heapSize = array.length, temp;
// 建堆
for (var i = Math.floor(heapSize / 2); i >= 0; i--) {
heapify(array, i, heapSize);
}
// 排序
for (var j = heapSize - 1; j >= 1; j--) {
temp = array[0];
array[0] = array[j];
array[j] = temp;
heapify(array, 0, --heapSize);
}
} else {
return 'array is not an Array!';
}
}
/* 維護堆的性質 @param arr 陣列 @param x 陣列下標 @param len 堆大小 */
function heapify(arr, x, len) {
if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
var l = 2 * x, r = 2 * x + 1, largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
} else {
return 'arr is not an Array or x is not a number!';
}
}
複雜度:最佳、最壞、平均皆為 O(n log n),且是原地排序,這也是它最大的優勢。
原理:建立在合併操作上的有效排序,是分治法非常典型的應用,且為穩定排序。做法是讓每個子序列各自有序,再讓子序列之間有序;把兩個有序表合成一個有序表即稱為 2 路合併。
步驟:
1. 把長度 n 的序列分成兩個長度 n/2 的子序列;
2. 對兩個子序列分別進行合併排序;
3. 把兩個已排序的子序列合併成最終序列。
function mergeSort(array, p, r) {
if (p < r) {
var q = Math.floor((p + r) / 2);
mergeSort(array, p, q);
mergeSort(array, q + 1, r);
merge(array, p, q, r);
}
}
function merge(array, p, q, r) {
var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0;
for (var i = 0; i < n1; i++) {
left[i] = array[p + i];
}
for (var j = 0; j < n2; j++) {
right[j] = array[q + 1 + j];
}
left[n1] = right[n2] = Number.MAX_VALUE;
for (var k = p; k <= r; k++) {
if (left[m] <= right[n]) {
array[k] = left[m];
m++;
} else {
array[k] = right[n];
n++;
}
}
}
複雜度:最佳 O(n)、最壞與平均 O(n log n)。代價是需要 O(n) 的額外空間。
原理:假設輸入資料服從均勻分布,把它們分派到有限數量的桶裡,每個桶各自排序(可再使用其他排序演算法或遞迴使用桶排序),最後依序串接。
步驟:
1. 建立定量的空桶陣列;
2. 走訪輸入資料,逐一放入對應的桶;
3. 對每個非空桶排序;
4. 依序把非空桶中排好的資料串接起來。
/* 桶排序 @param array 陣列 @param num 桶的數量 */
function bucketSort(array, num) {
if (array.length <= 1) {
return array;
}
var len = array.length, buckets = [], result = [],
min = max = array[0], regex = /^[1-9]+[0-9]*$/, space, n = 0;
num = num || ((num > 1 && regex.test(num)) ? num : 10);
for (var i = 1; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
space = (max - min + 1) / num;
for (var j = 0; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) {
// 非空桶:插入排序
var k = buckets[index].length - 1;
while (k >= 0 && buckets[index][k] > array[j]) {
buckets[index][k + 1] = buckets[index][k];
k--;
}
buckets[index][k + 1] = array[j];
} else {
// 空桶:初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
複雜度:最好情況可達線性 O(n)。整體時間取決於「各桶內部排序」的複雜度,其餘部分皆為 O(n)。桶切得越小,桶內資料越少、排序越快,但空間消耗隨之上升。
原理:穩定的排序演算法。它額外配置一個陣列 C,其中第 i 個元素代表待排序陣列 A 中「值等於 i」的元素個數,再依 C 把 A 的元素放到正確位置。它只能處理整數。
步驟:
1. 找出待排序陣列的最大與最小值;
2. 統計每個值 i 出現的次數,存入 C 的第 i 項;
3. 對所有計數做累加(從 C 第一項開始,每項加上前一項);
4. 反向填目標陣列:把元素 i 放到新陣列第 C(i) 項,每放一個就將 C(i) 減一。
function countingSort(array) {
var len = array.length, B = [], C = [], min = max = array[0];
for (var i = 0; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
}
for (var j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
}
for (var k = len - 1; k >= 0; k--) {
B[C[array[k]] - 1] = array[k];
C[array[k]]--;
}
return B;
}
複雜度:當輸入是 n 個介於 0 到 k 的整數時,執行時間為 O(n + k)。計數排序不是比較排序,因此速度可快過任何比較型排序。但用來計數的陣列 C 長度取決於資料值域(最大值減最小值加一),若值域很龐大,時間與記憶體消耗都會失控。
實務上的判斷很單純:一般情況直接用 JS 原生的 Array.prototype.sort()(現代引擎內部多為 TimSort 或混合策略),只有在需要穩定排序、限定整數值域、或資料量極大而無法全部載入記憶體時,才需要自己動手實作特定演算法。理解這些實作的價值,主要在於面試與在特殊場景下做出正確取捨。