山西建设投资集团有限公司优化营商环境条例

作为前端开发者，排序算法是我们必须掌握的基础知识。无论是在面试中，还是在实际开发中处理数据展示时，排序都是一个常见需求。今天，我将用通俗易懂的方式，带你了解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)	✅

总结

1. 简单排序：冒泡、选择、插入排序适合小规模数据或学习理解
2. 高效排序：归并、堆、快速排序适合大规模数据
3. 特殊排序：计数、桶、基数排序适合特定场景(整数、浮点数等)

在实际开发中，JavaScript的Array.prototype.sort()方法已经足够高效，它通常使用快速排序或归并排序的变体。但理解这些底层算法原理，能帮助我们更好地解决问题和优化代码。

希望这篇通俗易懂的排序算法指南对你有所帮助！

---

推荐更多阅读内容
掌握这些JavaScript技巧，让你的编码效率飙升！
JavaScript 字符串字符删除方法大揭秘
正向代理与反向代理：傻傻分不清楚
JavaScript分钟转时间格式（小时+分钟）的方法及应用
彻底理解 Object.entries() + map()：如何把对象转换成指定格式数组？
深入理解 window.open：用法、参数、兼容性与安全实践
彻底清除和禁用浏览器输入框历史记录的终极指南
JavaScript 开发中的高效技巧与基础知识解析