JavaScript 中常用排序方法的性能对比和分析

一、原生数组排序方法

1.Array.prototype.sort()

javascript

// 默认排序（按字符串Unicode码点） arr.sort() // 自定义比较函数 arr.sort((a, b) => a - b) // 数字升序

• 时间复杂度：

  • V8引擎：使用Timsort（归并+插入）

  • 平均/最坏情况：O(n log n)

  • 最佳情况：O(n)

• 空间复杂度：O(n)（稳定排序需要额外空间）

• 特点：稳定排序，适合大多数场景

二、经典排序算法实现

2.快速排序

javascript

function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[Math.floor(arr.length / 2)]; const left = arr.filter(x => x < pivot); const middle = arr.filter(x => x === pivot); const right = arr.filter(x => x > pivot); return quickSort(left).concat(middle, quickSort(right)); }

• 平均时间复杂度：O(n log n)

• 最坏情况：O(n²)（已排序数组）

• 空间复杂度：O(log n) ~ O(n)

• 特点：原地排序，不稳定

3.归并排序

javascript

function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid))); }

• 时间复杂度：O(n log n)

• 空间复杂度：O(n)

• 特点：稳定排序，适合链表

4.堆排序

javascript

function heapSort(arr) { // 建堆 for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // 排序 for (let i = arr.length - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; heapify(arr, i, 0); } return arr; }

• 时间复杂度：O(n log n)

• 空间复杂度：O(1)

• 特点：原地排序，不稳定

三、简单但低效的排序

5.冒泡排序

javascript

function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; }

• 时间复杂度：O(n²)

• 特点：实现简单，适合教学

6.插入排序

javascript

function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; }

• 最佳情况：O(n)（已排序）

• 最坏情况：O(n²)

• 特点：对小数组或基本有序数组高效

四、性能对比数据

以下是在 Chrome 119 中对 10,000 个随机整数的测试结果：

五、选择建议

1.日常使用

javascript

// 99% 的场景使用原生 sort arr.sort((a, b) => a - b);

2.特殊场景

• 小数组 (n < 10)：插入排序可能更快

• 几乎有序的数据：插入排序或冒泡排序

• 内存敏感：堆排序（原地排序）

• 需要稳定性：归并排序或 Timsort

3.现代 JavaScript 优化

javascript

// 使用 TypedArray 提高数值排序性能 const float64Array = new Float64Array([3, 1, 2]); float64Array.sort(); // 使用高度优化的底层实现 // Web Workers 并行处理大数据 if (window.Worker) { const worker = new Worker('sort-worker.js'); worker.postMessage(largeArray); }

关联阅读推荐

TypedArray 详解

---

什么是 TypedArray

TypedArray是 JavaScript 中处理二进制数据的对象，它提供了类似数组的视图来访问原始二进制缓冲区中的数据。

核心特点：

• 类型化：每个元素都有固定的数据类型（如 Int8、Uint32、Float64 等）

• 高性能：直接操作内存，避免了 JavaScript 对象的开销

• 固定长度：创建后长度不可变

• 内存高效：数据在内存中连续存储

TypedArray 类型

类型	字节长度	数值范围	描述
Int8Array	1	-128 ~ 127	8位有符号整数
Uint8Array	1	0 ~ 255	8位无符号整数
Uint8ClampedArray	1	0 ~ 255	8位无符号整数（限制范围）
Int16Array	2	-32768 ~ 32767	16位有符号整数
Uint16Array	2	0 ~ 65535	16位无符号整数
Int32Array	4	-2³¹ ~ 2³¹-1	32位有符号整数
Uint32Array	4	0 ~ 2³²-1	32位无符号整数
Float32Array	4	±1.2×10⁻³⁸ ~ ±3.4×10³⁸	32位浮点数
Float64Array	8	±5.0×10⁻³²⁴ ~ ±1.8×10³⁰⁸	64位浮点数
BigInt64Array	8	-2⁶³ ~ 2⁶³-1	64位有符号大整数
BigUint64Array	8	0 ~ 2⁶⁴-1	64位无符号大整数

4.实际考虑因素

javascript

// 根据数据特性选择 function smartSort(arr) { if (arr.length < 10) { return insertionSort(arr); } else if (isAlmostSorted(arr)) { return bubbleSort(arr); } else { return arr.sort((a, b) => a - b); } }

六、最佳实践总结

1. 优先使用Array.prototype.sort()- V8 的 Timsort 高度优化

2. 避免自己实现排序算法- 除非有特殊需求

3. 考虑数据特征- 数据量、有序程度、数据类型

4. 使用适当的数据结构- 有时不需要排序，用 Map/Set 更高效

5. 大数据集考虑分治- 分批排序或使用 Web Workers

原生sort()方法在绝大多数情况下都是最佳选择，除非你有明确的性能瓶颈和特殊需求。

关联阅读推荐

JavaScript 原生 sort() 方法详解