javascript排序算法如何实现_有哪些常见的排序方法

JavaScript排序需手写以避免sort()默认字符串排序错误；冒泡排序稳定但慢，快排平均O(n log n)但不稳定，归并排序稳定且复杂度恒定O(n log n)，原生sort不稳定，对象排序需自定义比较函数。

JavaScript 中实现排序算法，核心是理解每种算法的逻辑，并用 JS 语法表达出来。数组的 sort() 方法虽方便，但默认按字符串 Unicode 码点排序，处理数字时容易出错（如 [10, 2, 33].sort() 得到 [10, 2, 33]），所以掌握手写排序对理解数据结构、调试和面试都很重要。

冒泡排序（稳定、简单、适合小数据）

原理是重复遍历数组，两两比较相邻元素，把较大（或较小）的“浮”到一端。每轮确定一个极值位置，共需 n−1 轮。

关键点：外层控制轮数，内层控制比较范围（每轮减少一个末位）；可加优化——若某轮无交换，说明已有序，提前退出。

示例代码：

function bubbleSort(arr) {
  const res = [...arr];
  const n = res.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (res[j] > res[j + 1]) {
        [res[j], res[j + 1]] = [res[j + 1], res[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return res;
}

快速排序（高效、常用、分治思想）

选一个基准值（pivot），将数组分为三部分：小于 pivot、等于 pivot、大于 pivot，再递归排序前后两部分。平均时间复杂度 O(n log n)，原地排序但不稳定。

注意：避免最坏情况（已排序数组选首/尾为 pivot → O(n²)），可用随机选 pivot 或三数取中法优化。

简洁实现（非原地）：

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(Math.random() * arr.length)];
  const left = arr.filter(x => x < pivot);
  const mid = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), ...mid, ...quickSort(right)];
}

归并排序（稳定、适合大数据、分治+合并）

先递归拆分数组至单元素，再两两合并（合并时保持有序）。时间复杂度稳定 O(n log n)，但需要 O(n) 额外空间。

合并操作是重点：用两个指针分别遍历左右子数组，取较小值推入结果，剩余部分直接拼接。

示例：

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) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}

其他实用排序技巧与场景

JavaScript 开发中不总需要手写排序，但要会用对、调得准：

数字排序别忘传比较函数：[3, 1, 10].sort((a, b) => a - b)，避免字符串误排
对象数组按字段排序：users.sort((a, b) => a.age - b.age) 或用 localeCompare() 处理字符串
降序/多级排序：先主字段，相等再比次字段，如 (a, b) => b.score - a.score || a.name.localeCompare(b.name)
原生 sort 是不稳定排序（ECMAScript 规范未保证稳定性），如需稳定，优先选归并排序或用索引辅助