你是否在前端面試中遇到過排序算法實現的問題？是否想快速掌握常見排序算法的JavaScript實現？本文將帶你深入學習算法/算法.md中提供的8種排序算法，從基礎到進階，助你輕鬆應對面試挑戰。讀完本文，你將能夠理解並實現冒泡排序、選擇排序、插入排序、希爾排序、歸併排序、快速排序、堆排序和基數排序，並瞭解它們的時間複雜度、空間複雜度和穩定性。
排序算法概覽
排序算法是計算機科學中的基礎，也是前端面試的常見考點。算法/算法.md中詳細介紹了8種常用排序算法，它們各有特點，適用於不同的場景。下面是這些算法的基本信息對比：
|
算法名稱
|
平均時間複雜度
|
最壞時間複雜度
|
空間複雜度
|
穩定性
|
|
冒泡排序
|
O(n²)
|
O(n²)
|
O(1)
|
穩定
|
|
選擇排序
|
O(n²)
|
O(n²)
|
O(1)
|
不穩定
|
|
插入排序
|
O(n²)
|
O(n²)
|
O(1)
|
穩定
|
|
希爾排序
|
O(nlogn)
|
O(n²)
|
O(1)
|
不穩定
|
|
歸併排序
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
穩定
|
|
快速排序
|
O(nlogn)
|
O(n²)
|
O(logn)
|
不穩定
|
|
堆排序
|
O(nlogn)
|
O(nlogn)
|
O(1)
|
不穩定
|
|
基數排序
|
O(nk)
|
O(nk)
|
O(n)
|
穩定
|
基礎排序算法
冒泡排序
冒泡排序的基本思想是對相鄰的元素進行兩兩比較，順序相反則進行交換，每一趟會將最小或最大的元素“浮”到頂端。算法/算法.md中提供了優化後的冒泡排序實現：
function bubbleSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let lastIndex = arr.length - 1;
while (lastIndex > 0) { // 當最後一個交換的元素為第一個時，説明後面全部排序完畢
let flag = true, k = lastIndex;
for (let j = 0; j < k; j++) {
if (arr[j] > arr[j + 1]) {
flag = false;
lastIndex = j; // 設置最後一次交換元素的位置
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
if (flag) break;
}
}該實現有兩處優化：一是記錄當前循環中是否發生了交換，如果沒有則説明序列已排序完成；二是記錄最後一次交換元素的位置，該位置之後的元素已排序完成，無需再比較。
選擇排序
選擇排序的基本思想是每一趟從待排序的數據元素中選擇最小（或最大）的一個元素作為首元素，直到所有元素排完為止。算法/算法.md中的實現如下：
function selectSort(array) {
let length = array.length;
if (!Array.isArray(array) || length <= 1) return;
for (let i = 0; i < length - 1; i++) {
let minIndex = i; // 設置當前循環最小元素索引
for (let j = i + 1; j < length; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
return array;
}
function swap(array, left, right) {
var temp = array[left];
array[left] = array[right];
array[right] = temp;
}選擇排序的特點是交換次數少，但不穩定，因為每次交換可能會改變相等元素的相對順序。
插入排序
直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去。算法/算法.md中將其比喻為撲克牌思想：
function insertSort(array) {
let length = array.length;
if (!Array.isArray(array) || length <= 1) return;
for (let i = 1; i < length; i++) {
let temp = array[i]; // 保存當前需要排序的元素
let j = i;
while (j -1 >= 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
}插入排序在數組基本有序的情況下性能最好，時間複雜度可接近O(n)。
進階排序算法
希爾排序
希爾排序是插入排序的改進版，它將數組按下標的一定增量分組，對每組使用直接插入排序算法排序，隨着增量逐漸減少，每組包含的元素越來越多，當增量減至1時，整個數組恰被分成一組。算法/算法.md中的實現如下：
function hillSort(array) {
let length = array.length;
if (!Array.isArray(array) || length <= 1) return;
for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
for (let i = gap; i < length; i++) {
let temp = array[i];
let j = i;
while (j - gap >= 0 && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
return array;
}希爾排序的時間複雜度取決於增量序列的選擇，平均時間複雜度為O(nlogn)。
歸併排序
歸併排序採用分治策略，將數組分成兩部分，分別排序後再合併。算法/算法.md中的實現如下：
function mergeSort(array) {
let length = array.length;
if (!Array.isArray(array) || length === 0) return;
if (length === 1) {
return array;
}
let mid = parseInt(length >> 1),
left = array.slice(0, mid),
right = array.slice(mid, length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(leftArray, rightArray) {
let result = [],
leftLength = leftArray.length,
rightLength = rightArray.length,
il = 0,
ir = 0;
while (il < leftLength && ir < rightLength) {
if (leftArray[il] < rightArray[ir]) {
result.push(leftArray[il++]);
} else {
result.push(rightArray[ir++]);
}
}
while (il < leftLength) result.push(leftArray[il++]);
while (ir < rightLength) result.push(rightArray[ir++]);
return result;
}歸併排序是穩定的排序算法，但需要額外的O(n)空間。
快速排序
快速排序的基本思想是通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序。算法/算法.md中的實現採用填空法：
function quickSort(array, start, end) {
let length = array.length;
if (!Array.isArray(array) || length <= 1 || start >= end) return;
let index = partition(array, start, end);
quickSort(array, start, index - 1);
quickSort(array, index + 1, end);
}
function partition(array, start, end) {
let pivot = array[start];
while (start < end) {
while (array[end] >= pivot && start < end) end--;
array[start] = array[end];
while (array[start] < pivot && start < end) start++;
array[end] = array[start];
}
array[start] = pivot;
return start;
}快速排序是實際應用中最常用的排序算法之一，它的平均時間複雜度為O(nlogn)，但最壞情況下會退化為O(n²)。
堆排序
堆排序利用堆這種數據結構進行排序，它將待排序序列構造成一個大頂堆，此時整個序列的最大值就是堆頂的根節點，將其與末尾元素交換，然後將剩餘n-1個元素重新構造成一個堆，如此反覆執行。算法/算法.md中的實現如下：
function heapSort(array) {
let length = array.length;
if (!Array.isArray(array) || length <= 1) return;
buildMaxHeap(array);
for (let i = length - 1; i > 0; i--) {
swap(array, 0, i);
adjustMaxHeap(array, 0, i);
}
return array;
}
function adjustMaxHeap(array, index, heapSize) {
let iMax = index, iLeft = 2 * index + 1, iRight = 2 * index + 2;
while (true) {
if (iLeft < heapSize && array[iMax] < array[iLeft]) iMax = iLeft;
if (iRight < heapSize && array[iMax] < array[iRight]) iMax = iRight;
if (iMax !== index) {
swap(array, index, iMax);
index = iMax;
} else break;
}
}
function buildMaxHeap(array) {
let length = array.length, iParent = parseInt(length >> 1) - 1;
for (let i = iParent; i >= 0; i--) adjustMaxHeap(array, i, length);
}
function swap(array, i, j) {
let temp = array[i];
array[i] = array[j];
array[j] = temp;
}堆排序的時間複雜度為O(nlogn)，空間複雜度為O(1)，但由於緩存局部性較差，實際性能可能不如快速排序。
基數排序
基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。算法/算法.md中的實現如下：
function radixSort(array) {
let length = array.length;
if (!Array.isArray(array) || length <= 1) return;
let bucket = [], max = array[0], loop;
for (let i = 1; i < length; i++) if (array[i] > max) max = array[i];
loop = (max + '').length;
for (let i = 0; i < 10; i++) bucket[i] = [];
for (let i = 0; i < loop; i++) {
for (let j = 0; j < length; j++) {
let str = array[j] + '';
if (str.length >= i + 1) {
let k = parseInt(str[str.length - 1 - i]);
bucket[k].push(array[j]);
} else bucket[0].push(array[j]);
}
array.splice(0, length);
for (let i = 0; i < 10; i++) {
let t = bucket[i].length;
for (let j = 0; j < t; j++) array.push(bucket[i][j]);
bucket[i] = [];
}
}
return array;
}基數排序的時間複雜度為O(nk)，其中k為最大元素的位數，適用於整數排序。
排序算法選擇指南
在實際應用中，如何選擇合適的排序算法呢？算法/算法.md中總結了以下幾點：
- 快速排序在完全無序的情況下效果最好，時間複雜度為O(nlogn)，在有序情況下效果最差，時間複雜度為O(n²)。
- 初始數據集的排列順序對算法的性能無影響的有堆排序，直接選擇排序，歸併排序，基數排序。
- 數組元素基本有序的情況下，插入排序效果最好，因為這樣只需要比較大小，不需要移動，時間複雜度趨近於O(n)。
- 如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用堆排序方法最快。
