javascript中的排序算法有哪些_如何实现快速排序或归并排序-js教程-PHP中文网

javascript中的排序算法有哪些_如何实现快速排序或归并排序

狼影

发布： 2025-12-17 19:43:48

原创

174人浏览过

JavaScript常用排序算法中，快速排序是高效O(n log n)的分治算法，选基准值划分数组并递归排序，原地实现但最坏O(n²)，不稳定，适合无序数据。

javascript中的排序算法有哪些_如何实现快速排序或归并排序

JavaScript 中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。其中，快速排序和归并排序是两种高效、实用的 O(n log n) 级别排序算法，适合处理中大型数组。它们在原生 Array.prototype.sort() 的底层实现中也常被参考（V8 引擎目前主要用 Timsort，是归并+插入的混合优化版本）。

快速排序（Quicksort）原理与实现

核心思想是“分治”：选一个基准值（pivot），将数组分为三部分——小于 pivot 的、等于 pivot 的、大于 pivot 的，再递归排序前后两部分。

不依赖额外空间（原地排序），但最坏时间复杂度为 O(n²)，平均为 O(n log n)
不稳定排序（相等元素的相对位置可能改变）
适合内存受限、数据基本无序的场景

简易实现（非原地，更易理解）：

function quickSort(arr) {
  if (arr.length <= 1) return arr;
<p>const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
const equal = [];</p><p>for (let val of arr) {
if (val < pivot) left.push(val);
else if (val > pivot) right.push(val);
else equal.push(val);
}</p><p>return [...quickSort(left), ...equal, ...quickSort(right)];
}
// 使用示例
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]

登录后复制

归并排序（Merge Sort）原理与实现

也是分治法：把数组不断二分直到单元素，再逐层合并两个已排序子数组，合并时按顺序归并。

立即学习“Java免费学习笔记（深入）”；

歌者PPT

歌者PPT，AI 写 PPT 永久免费

358

查看详情

稳定排序（相等元素顺序不变）
时间复杂度稳定为 O(n log n)，但需 O(n) 额外空间
适合链表排序或需要稳定性的场景（如按多个字段排序）

递归 + 合并实现：

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
<p>const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));</p><p>return merge(left, right);
}</p><p>function merge(left, right) {
let result = [];
let i = 0, j = 0;</p><p>while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}</p><p>return result.concat(left.slice(i)).concat(right.slice(j));
}
// 使用示例
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82]

登录后复制