作為前端開發者，排序算法是我們必須掌握的基礎知識。無論是在面試中，還是在實際開發中處理數據展示時，排序都是一個常見需求。今天，我將用通俗易懂的方式，帶你了解JavaScript中最常見的10種排序算法。
1. 冒泡排序 - 最直觀的排序方式
冒泡排序可能是最容易理解的排序算法了。它的基本思想是：重復地遍歷要排序的數組，一次比較兩個元素，如果它們的順序錯誤就交換它們。
想象一下水中的氣泡，較大的氣泡會慢慢浮到水面。在冒泡排序中，較大的元素會"冒泡"到數組的末端。
function bubbleSort(arr) {const n = arr.length;for (let i = 0; i < n - 1; i++) {let swapped = false; // 優化：如果一輪沒有交換，說明已經有序for (let j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6解構賦值交換元素swapped = true;}}if (!swapped) break; // 如果沒有發生交換，提前結束}return arr;
}
特點：
- 時間復雜度：最好情況O(n)(已經有序)，最壞O(n2)
- 空間復雜度：O(1)(原地排序)
- 穩定排序(相等元素不會改變相對位置)
適用場景：數據量小，或者作為學習排序的入門算法。
2. 選擇排序 - 每次選擇最小的元素
選擇排序的思想是：每次從未排序部分選擇最小的元素，放到已排序部分的末尾。
function selectionSort(arr) {const n = arr.length;for (let i = 0; i < n; i++) {let minIndex = i; // 假設當前索引是最小值的索引for (let j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 找到更小的值，更新索引}}[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交換}return arr;
}
特點：
- 時間復雜度：始終O(n2)
- 空間復雜度：O(1)
- 不穩定排序(可能改變相等元素的相對位置)
適用場景：數據量小，且不要求穩定排序的情況。
3. 插入排序 - 撲克牌排序方式
插入排序類似于我們整理撲克牌的方式：將數組分為已排序和未排序兩部分，每次從未排序部分取出一個元素，插入到已排序部分的正確位置。
function insertionSort(arr) {for (let i = 1; i < arr.length; i++) {let current = arr[i]; // 當前要插入的元素let j = i - 1;// 將比current大的元素向后移動while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}arr[j + 1] = current; // 插入到正確位置}return arr;
}
特點：
- 時間復雜度：最好O(n)(已經有序)，最壞O(n2)
- 空間復雜度：O(1)
- 穩定排序
適用場景：小規模數據，或者基本有序的數據。
4. 希爾排序 - 插入排序的改進版
希爾排序是插入排序的改進版本，也稱為"縮小增量排序"。它通過將原始數組分成若干子序列進行插入排序，然后逐步縮小增量直至整個數組有序。
function shellSort(arr) {let gap = Math.floor(arr.length / 2); // 初始步長while (gap > 0) {for (let i = gap; i < arr.length; i++) {let temp = arr[i];let j = i;// 對子序列進行插入排序while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}gap = Math.floor(gap / 2); // 縮小步長}return arr;
}
特點：
- 時間復雜度：平均O(n^1.3)，比O(n2)好很多
- 空間復雜度：O(1)
- 不穩定排序
適用場景：中等規模的數據排序。
5. 歸并排序 - 分而治之的經典算法
歸并排序采用分治法的思想：將數組分成兩半，分別排序，然后將兩個有序數組合并成一個有序數組。
function mergeSort(arr) {if (arr.length <= 1) return arr; // 基線條件const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid)); // 遞歸排序左半部分const right = mergeSort(arr.slice(mid)); // 遞歸排序右半部分return merge(left, right); // 合并兩個有序數組
}function merge(left, right) {const result = [];while (left.length && right.length) {// 比較兩個數組的第一個元素，取較小的放入結果result.push(left[0] < right[0] ? left.shift() : right.shift());}return result.concat(left, right); // 合并剩余元素
}
特點：
- 時間復雜度：始終O(n log n)
- 空間復雜度：O(n)(需要額外的存儲空間)
- 穩定排序
適用場景：大規模數據排序，特別是需要穩定排序的情況。
6. 堆排序 - 基于二叉堆的排序
堆排序是一種基于**二叉堆(優先隊列)**的排序算法。它首先構建一個最大堆，然后不斷取出堆頂元素(最大值)放到數組末尾。
function heapSort(arr) {const n = arr.length;// 構建最大堆function heapify(i, heapSize) {let largest = i; // 初始化最大值為當前節點const left = 2 * i + 1; // 左子節點const right = 2 * i + 2; // 右子節點// 如果左子節點存在且大于當前最大值if (left < heapSize && arr[left] > arr[largest]) {largest = left;}// 如果右子節點存在且大于當前最大值if (right < heapSize && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是當前節點，交換并繼續堆化if (largest !== i) {[arr[i], arr[largest]] = [arr[largest], arr[i]];heapify(largest, heapSize);}}// 構建最大堆(從最后一個非葉子節點開始)for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {heapify(i, n);}// 逐個取出堆頂元素for (let i = n - 1; i > 0; i--) {[arr[0], arr[i]] = [arr[i], arr[0]]; // 將堆頂元素(最大值)與當前末尾交換heapify(0, i); // 對剩余元素重新堆化}return arr;
}
特點：
- 時間復雜度：始終O(n log n)
- 空間復雜度：O(1)
- 不穩定排序
適用場景：需要高效排序且內存有限的情況。
7. 快速排序 - 最常用的排序算法
快速排序也是一種分治法的排序算法。它選擇一個"基準"元素，將數組分為兩部分：小于基準的和大于基準的，然后遞歸地對這兩部分進行排序。
function quickSort(arr) {if (arr.length <= 1) return arr; // 基線條件const pivot = arr[0]; // 選擇第一個元素作為基準(簡單實現)const left = []; // 小于基準的元素const right = []; // 大于基準的元素for (let i = 1; i < arr.length; i++) {if (arr[i] < pivot) {left.push(arr[i]);} else {right.push(arr[i]);}}return [...quickSort(left), pivot, ...quickSort(right)]; // 遞歸排序并合并
}
更高效的實現(原地分區)：
function quickSort(arr, left = 0, right = arr.length - 1) {if (left < right) {const pivotIndex = partition(arr, left, right); // 獲取分區點quickSort(arr, left, pivotIndex - 1); // 遞歸排序左半部分quickSort(arr, pivotIndex + 1, right); // 遞歸排序右半部分}return arr;
}function partition(arr, left, right) {const pivot = arr[right]; // 選擇最右邊的元素作為基準let i = left; // i是小于基準的元素的邊界for (let j = left; j < right; j++) {if (arr[j] < pivot) {[arr[i], arr[j]] = [arr[j], arr[i]]; // 交換元素i++; // 移動邊界}}[arr[i], arr[right]] = [arr[right], arr[i]]; // 將基準放到正確位置return i; // 返回基準的索引
}
特點：
- 時間復雜度：平均O(n log n)，最壞O(n2)(當數組已經有序時)
- 空間復雜度：O(log n)(遞歸調用棧)
- 不穩定排序
適用場景：大規模數據排序，追求性能的情況。
8. 計數排序 - 非比較排序算法
計數排序是一種非比較排序算法，適用于整數排序。它的基本思想是：統計每個元素出現的次數，然后根據統計結果重建有序數組。
function countingSort(arr, maxVal) {const count = new Array(maxVal + 1).fill(0); // 統計每個元素出現的次數for (let num of arr) {count[num]++;}const result = [];for (let i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {result.push(i); // 根據統計結果重建數組}}return result;
}
特點：
- 時間復雜度：O(n + k)(k是數據的范圍)
- 空間復雜度：O(k)
- 穩定排序(如果實現得當)
適用場景：數據是整數且范圍不大的情況。
9. 桶排序 - 分配到多個桶中排序
桶排序將元素分散到多個"桶"中，每個桶內部進行排序，最后合并所有桶的結果。
function bucketSort(arr, bucketSize = 5) {if (arr.length <= 1) return arr;const min = Math.min(...arr);const max = Math.max(...arr);const bucketCount = Math.floor((max - min) / bucketSize) + 1; // 計算桶的數量const buckets = Array.from({ length: bucketCount }, () => []); // 創建桶// 將元素分配到各個桶中for (let num of arr) {const index = Math.floor((num - min) / bucketSize);buckets[index].push(num);}// 對每個桶進行排序并合并結果return buckets.flatMap(bucket => insertionSort(bucket)); // 這里使用了插入排序
}
特點：
- 時間復雜度：O(n + k)，最壞O(n2)(當所有元素都在一個桶中)
- 空間復雜度：O(n + k)
- 穩定排序(取決于桶內使用的排序算法)
適用場景：數據分布均勻的情況，特別是浮點數排序。
10. 基數排序 - 按位比較的排序
基數排序是一種非比較排序算法，它按照數字的位數從低位到高位依次排序。
function radixSort(arr) {const max = Math.max(...arr);let exp = 1; // 從個位開始while (Math.floor(max / exp) > 0) {countingByDigit(arr, exp); // 按當前位排序exp *= 10; // 移動到下一位}return arr;
}function countingByDigit(arr, exp) {const output = new Array(arr.length).fill(0);const count = new Array(10).fill(0); // 0-9的數字// 統計當前位數字出現的次數for (let num of arr) {count[Math.floor(num / exp) % 10]++;}// 計算累計次數for (let i = 1; i < 10; i++) {count[i] += count[i - 1];}// 從后向前遍歷，保證穩定性for (let i = arr.length - 1; i >= 0; i--) {const digit = Math.floor(arr[i] / exp) % 10;output[--count[digit]] = arr[i];}// 將排序結果復制回原數組for (let i = 0; i < arr.length; i++) {arr[i] = output[i];}
}
特點：
- 時間復雜度：O(nk)(k是最大數字的位數)
- 空間復雜度：O(n + k)
- 穩定排序
適用場景：非負整數排序，特別是位數不多的情況。
排序算法性能對比
| 排序算法 | 最好時間復雜度 | 最壞時間復雜度 | 平均時間復雜度 | 空間復雜度 | 穩定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | ? |
| 選擇排序 | O(n2) | O(n2) | O(n2) | O(1) | ? |
| 插入排序 | O(n) | O(n2) | O(n2) | O(1) | ? |
| 希爾排序 | O(n log n) | O(n2) | O(n^1.3) | O(1) | ? |
| 歸并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ? |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ? |
| 快速排序 | O(n log n) | O(n2) | O(n log n) | O(log n) | ? |
| 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | ? |
| 桶排序 | O(n + k) | O(n2) | O(n + k) | O(n + k) | ? |
| 基數排序 | O(nk) | O(nk) | O(nk) | O(n + k) | ? |
總結
- 簡單排序：冒泡、選擇、插入排序適合小規模數據或學習理解
- 高效排序：歸并、堆、快速排序適合大規模數據
- 特殊排序：計數、桶、基數排序適合特定場景(整數、浮點數等)
在實際開發中，JavaScript的Array.prototype.sort()方法已經足夠高效，它通常使用快速排序或歸并排序的變體。但理解這些底層算法原理，能幫助我們更好地解決問題和優化代碼。
希望這篇通俗易懂的排序算法指南對你有所幫助！
推薦更多閱讀內容
掌握這些JavaScript技巧，讓你的編碼效率飆升！
JavaScript 字符串字符刪除方法大揭秘
正向代理與反向代理：傻傻分不清楚
JavaScript分鐘轉時間格式（小時+分鐘）的方法及應用
徹底理解Object.entries()+map()：如何把對象轉換成指定格式數組？
深入理解window.open：用法、參數、兼容性與安全實踐
徹底清除和禁用瀏覽器輸入框歷史記錄的終極指南
JavaScript 開發中的高效技巧與基礎知識解析
)
