一文全面了解JavaScript最常見(jiàn)的十種排序算法
在前端面試或日常開(kāi)發(fā)中，排序算法是既基礎(chǔ)又高頻的知識(shí)點(diǎn)內(nèi)容之一。常常會(huì)出現(xiàn)在開(kāi)發(fā)面試中，你可能在處理表格數(shù)據(jù)、排行榜、過(guò)濾器等功能時(shí)，都遇到過(guò)“需要排序”的情況。而選擇哪種排序算法，往往會(huì)影響性能與穩(wěn)定性的平衡。
為了幫助你徹底吃透排序算法，今天這篇文章，我?guī)痛蠹蚁到y(tǒng)梳理了一下了JavaScript 中最常見(jiàn)的 10 種排序方法，每種算法都包含核心原理，應(yīng)用場(chǎng)景，時(shí)間&空間復(fù)雜度等相關(guān)內(nèi)容。不管你是準(zhǔn)備面試，還是想知識(shí)查漏補(bǔ)缺，這份“排序算法全家桶”都值得收藏！
下面我們開(kāi)始今天的內(nèi)容吧。
1. 冒泡排序（Bubble Sort）
原理：每輪比較相鄰兩個(gè)元素，若順序錯(cuò)誤就交換，將“最大值”慢慢“冒泡”到最后。
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]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}冒泡排序的行為類(lèi)似一個(gè)雙重循環(huán)，外循環(huán)決定內(nèi)循環(huán)的次數(shù)，內(nèi)循環(huán)用于找到最大的數(shù)并將其放到外面。
適用場(chǎng)景：數(shù)據(jù)量小、初學(xué)者入門(mén)
時(shí)間復(fù)雜度：最好 O(n)，最壞 O(n2)空間復(fù)雜度：O(1)是否穩(wěn)定：是
2. 選擇排序（Selection Sort）
原理：每次選擇剩余數(shù)組中最小的元素，放到已排序部分的末尾。
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;
}選擇排序的行為與冒泡排序相反，它每一次遍歷都是找到最小的數(shù)放在前面。
適用場(chǎng)景：小規(guī)模排序，不追求穩(wěn)定
時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)是否穩(wěn)定： 否
3. 插入排序（Insertion Sort）
原理：每次將一個(gè)元素插入到前面有序序列的正確位置。
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i], j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}插入排序類(lèi)似選擇排序，也是將數(shù)組劃分為兩個(gè)區(qū)域，左邊的第一數(shù)為有序區(qū)域，右邊為無(wú)序區(qū)域，不同的是，插入排序的每次循環(huán)不是找最小數(shù)，而是直接將無(wú)序區(qū)的第一個(gè)數(shù)取出來(lái)，插入到有序區(qū)域適當(dāng)位置上。
適用場(chǎng)景：小規(guī)模、基本有序數(shù)據(jù)
時(shí)間復(fù)雜度：最好 O(n)，最壞 O(n2)空間復(fù)雜度：O(1)是否穩(wěn)定：是
4. 希爾排序（Shell Sort）
原理：分組插入排序，逐漸縮小步長(zhǎng)（gap）來(lái)優(yōu)化插入排序效率。
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], 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;
}希爾排序是希爾（Donald Shell）1959年提出的一種排序算法，是插入排序的改進(jìn)版，也稱(chēng)縮小增量排序。它是第一批沖破O(n2)的算法之一。
適用場(chǎng)景：中小型數(shù)組排序
時(shí)間復(fù)雜度：平均 O(n^1.3)空間復(fù)雜度：O(1)是否穩(wěn)定：否
5. 歸并排序（Merge Sort）
原理：遞歸分組、排序再合并，有較強(qiáng)的穩(wěn)定性。
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);
}適用場(chǎng)景：大型數(shù)據(jù)、追求穩(wěn)定性
時(shí)間復(fù)雜度：O(n log n)空間復(fù)雜度：O(n)是否穩(wěn)定：是
6. 堆排序（Heap Sort）
原理：構(gòu)建最大堆，每次取出堆頂（最大元素）放末尾。
function heapSort(arr) {
const n = arr.length;
function heapify(i, heapSize) {
let largest = i, left = 2 * i + 1, 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;
}堆排序是選擇排序的一種，它是不穩(wěn)定排序的一種。
適用場(chǎng)景：高效排序、內(nèi)存控制需求
時(shí)間復(fù)雜度：O(n log n)空間復(fù)雜度：O(1)是否穩(wěn)定：否
7. 快速排序（Quick Sort）
原理：選一個(gè)基準(zhǔn)，將小于它的放左邊，大于它的放右邊，遞歸處理。
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [], right = [];
for (let i = 1; i < arr.length; i++) {
(arr[i] < pivot ? left : right).push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}快速排序的對(duì)冒泡排序的一種改進(jìn)，一個(gè)基于分治法的排序。
適用場(chǎng)景：追求極致性能的排序任務(wù)
時(shí)間復(fù)雜度：平均 O(n log n)，最壞 O(n2)空間復(fù)雜度：O(log n)是否穩(wěn)定：否
8. 計(jì)數(shù)排序（Counting Sort）
原理：統(tǒng)計(jì)每個(gè)值出現(xiàn)的次數(shù)，重建數(shù)組。
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;
}適用場(chǎng)景：數(shù)據(jù)是整數(shù)，范圍不大
時(shí)間復(fù)雜度：O(n + k)空間復(fù)雜度：O(k)是否穩(wěn)定：是
9. 桶排序（Bucket Sort）
原理：將元素分散到多個(gè)“桶”中排序，最后合并。
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));
}適用場(chǎng)景：實(shí)數(shù)、數(shù)據(jù)分布均勻
時(shí)間復(fù)雜度：O(n + k)，最壞 O(n2)空間復(fù)雜度：O(n + k)是否穩(wěn)定：是
10. 基數(shù)排序（Radix Sort）
原理：按位比較，從最低位到最高位依次排序。
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);
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];
}適用場(chǎng)景：非負(fù)整數(shù)排序
時(shí)間復(fù)雜度：O(nk)空間復(fù)雜度：O(n + k)是否穩(wěn)定：是
排序算法性能對(duì)比表
排序算法 | 最好 | 最壞 | 平均 | 空間復(fù)雜度 | 穩(wěn)定性 |
冒泡排序 | 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) | ? |
計(jì)數(shù)排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | ? |
桶排序 | O(n + k) | O(n2) | O(n + k) | O(n + k) | ? |
基數(shù)排序 | O(nk) | O(nk) | O(nk) | O(n + k) | ? |
寫(xiě)在最后
排序算法看似“老生常談”，但在每一場(chǎng)真正的算法挑戰(zhàn)中，它們依然是最基礎(chǔ)的“武器”。掌握排序，不只是為了寫(xiě)出“排序函數(shù)”，更是提升你對(duì)數(shù)據(jù)結(jié)構(gòu)與算法思想的理解。
