在JavaScript开发中，排序算法是处理数据时不可或缺的基础技能。无论是前端展示数据、后端处理业务逻辑，还是算法竞赛或面试场景，掌握常见排序算法的实现原理和优化技巧都能显著提升代码效率。本文将系统梳理JavaScript中常用的排序算法，涵盖冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等经典方法，通过代码实现、时间复杂度分析和适用场景对比，帮助开发者构建完整的排序知识体系。
一、基础排序算法：理解排序的本质
基础排序算法通常以直观的逻辑实现，适合小规模数据或教学场景。它们的核心思想是通过比较和交换元素位置达到有序状态。
1. 冒泡排序（Bubble Sort）
冒泡排序通过多次遍历数组，每次比较相邻元素，将较大的值"冒泡"到数组末尾。其时间复杂度为O(n²)，空间复杂度为O(1)，是稳定性排序算法。
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6解构交换
}
}
}
return arr;
}
// 优化版：增加标志位减少无效遍历
function optimizedBubbleSort(arr) {
let swapped = true;
for (let i = 0; i arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
}
return arr;
}优化后的冒泡排序在最好情况下（已排序数组）时间复杂度降至O(n)，但平均和最坏情况仍为O(n²)。
2. 选择排序（Selection Sort）
选择排序每次遍历找到未排序部分的最小值，与当前位置交换。其时间复杂度恒为O(n²)，但交换次数少于冒泡排序。
function selectionSort(arr) {
const len = arr.length;
for (let i = 0; i 选择排序的不稳定性体现在相同值的元素可能因交换改变相对顺序。
3. 插入排序（Insertion Sort）
插入排序将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。对近乎有序的数组效率极高。
function insertionSort(arr) {
const len = arr.length;
for (let i = 1; i = 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}插入排序的时间复杂度为O(n²)，但最好情况下（已排序）可达O(n)，且空间复杂度为O(1)。
二、高效排序算法：分治思想的实践
高效排序算法通过分治策略将问题分解为子问题，显著降低时间复杂度，适合大规模数据排序。
1. 快速排序（Quick Sort）
快速排序采用"分而治之"策略，选择基准值（pivot）将数组分为小于和大于基准的两部分，递归排序子数组。平均时间复杂度为O(n log n)，最坏情况为O(n²)。
function quickSort(arr) {
if (arr.length = right) return;
const pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
return arr;
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j 快速排序的效率高度依赖基准值的选择，三数取中法可优化最坏情况。
2. 归并排序（Merge Sort）
归并排序将数组递归分为两半，分别排序后合并。其时间复杂度稳定为O(n log n)，但需要O(n)的额外空间。
function mergeSort(arr) {
if (arr.length 归并排序的稳定性使其适合处理包含复杂对象的数组。
3. 堆排序（Heap Sort）
堆排序利用二叉堆数据结构，先构建最大堆，然后反复取出堆顶元素并调整堆。时间复杂度为O(n log n)，空间复杂度为O(1)。
function heapSort(arr) {
const len = arr.length;
// 构建最大堆
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, len, i);
}
// 逐个提取元素
for (let i = len - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶和末尾
heapify(arr, i, 0); // 调整堆
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left arr[largest]) {
largest = left;
}
if (right arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}堆排序的不稳定性体现在相同值的元素可能因堆调整改变顺序。
三、特殊场景排序算法
1. 计数排序（Counting Sort）
计数排序适用于整数且范围较小的场景，通过统计每个元素的出现次数实现线性时间排序。
function countingSort(arr) {
const max = Math.max(...arr);
const min = Math.min(...arr);
const count = Array(max - min + 1).fill(0);
const output = Array(arr.length).fill(0);
arr.forEach(num => count[num - min]++);
for (let i = 1; i = 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}计数排序的时间复杂度为O(n + k)，其中k为数据范围。
2. 桶排序（Bucket Sort）
桶排序将数据分到有限数量的桶中，每个桶单独排序后合并。适用于均匀分布的浮点数。
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) return arr;
let min = Math.min(...arr);
let max = Math.max(...arr);
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets = Array.from({ length: bucketCount }, () => []);
arr.forEach(num => {
const bucketIndex = Math.floor((num - min) / bucketSize);
buckets[bucketIndex].push(num);
});
return buckets.flatMap(bucket => {
if (bucket.length > 1) {
return insertionSort(bucket); // 桶内使用插入排序
}
return bucket;
});
}四、JavaScript内置排序方法
JavaScript的Array.prototype.sort()方法默认按Unicode码点排序，可通过比较函数自定义排序逻辑。
const numbers = [3, 1, 4, 1, 5];
// 升序排序
numbers.sort((a, b) => a - b);
// 降序排序
numbers.sort((a, b) => b - a);
// 对象数组排序
const users = [{name: 'John', age: 25}, {name: 'Jane', age: 22}];
users.sort((a, b) => a.age - b.age);不同浏览器对sort()的实现可能不同（如V8使用Timsort变种），但均保证O(n log n)的平均时间复杂度。
五、算法选择指南
选择排序算法需考虑数据规模、数据特征和性能要求：
- 小规模数据（n ：插入排序或选择排序
- 近乎有序数据：插入排序
- 大规模数据：快速排序或归并排序
- 内存受限环境：堆排序
- 整数小范围数据：计数排序
- 稳定排序需求：归并排序或插入排序
六、性能优化技巧
- 对小规模子数组使用插入排序（快速排序优化）
- 三数取中法选择基准值（快速排序优化）
- 避免递归使用栈溢出（改用迭代实现）
- 利用TypedArray处理数值数据
- Web Worker多线程处理超大规模数据
关键词：JavaScript排序算法、冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、计数排序、桶排序、时间复杂度、空间复杂度、稳定性排序
简介：本文系统梳理JavaScript中常用的排序算法，涵盖冒泡排序、选择排序、插入排序等基础算法，以及快速排序、归并排序、堆排序等高效算法，详细分析各算法的实现原理、时间复杂度、空间复杂度和稳定性，并提供代码实现和优化建议，帮助开发者根据不同场景选择最适合的排序方案。
