作为前端开发者，排序算法是我们必须掌握的基础知识。无论是在面试中，还是在实际开发中处理数据展示时，排序都是一个常见需求。今天，我将用通俗易懂的方式，带你了解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(n²)
- 空间复杂度：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(n²)
- 空间复杂度：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(n²)
- 空间复杂度：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(n²)好很多
- 空间复杂度：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(n²)(当数组已经有序时)
- 空间复杂度：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(n²)(当所有元素都在一个桶中)
- 空间复杂度：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(n²) | O(n²) | O(1) | ✅ |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| 希尔排序 | O(n log n) | O(n²) | 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(n²) | O(n log n) | O(log n) | ❌ |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ |
| 桶排序 | O(n + k) | O(n²) | 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 开发中的高效技巧与基础知识解析
)
