快排与归并

快速排序（Quick Sort）和归并排序（Merge Sort）都是基于分治思想的高效排序算法，但它们在实现细节、性能特征和应用场景上有显著区别。以下是两者的主要区别：

核心思想

快速排序

• 通过选择一个基准元素（pivot），将数组分成两部分：左半部分 ≤ 基准 ≤ 右半部分。
• 递归地对左右子数组进行同样的操作，直到数组有序。
• 核心操作是分区（Partition），时间复杂度低但可能不均匀。

归并排序

• 将数组均等分成两半，递归排序每一半，再将两个有序子数组合并成一个有序数组。
• 核心操作是合并（Merge），需要额外的空间和时间进行合并。

时间复杂度

平均时间复杂度：两者均为 O(n log n)。

最坏时间复杂度：

• 快速排序：O(n²)（当分区极度不平衡时，如已有序数组且选到最差基准）。
• 归并排序：稳定为 O(n log n)，不受输入数据影响。

空间复杂度

快速排序：原地排序（in-place），仅需递归栈空间，平均 O(log n)（递归深度）；若实现为非递归版本，可优化为 O(1) 空间（但实际中很少使用）。

归并排序：需要额外空间合并子数组，空间复杂度为 O(n)；若优化为链表实现或自底向上迭代版本，空间复杂度可降至 O(1)。

稳定性

快速排序不稳定，分区过程中可能打乱相同元素的原始顺序。

归并排序稳定（如果合并时对相等元素优先保留原顺序）。

性能关键点

快速排序：

• 性能依赖基准的选择。优化方法包括：三数取中、随机化基准等。
• 实际应用中常数因子更小，通常比归并排序更快。

归并排序：

• 性能依赖合并操作的效率，对内存访问模式友好（顺序访问）。
• 适合处理大数据或外部排序（如磁盘文件排序）。

应用场景

快速排序：适用于内存排序，尤其是对速度要求高、数据随机的场景；如 C 标准库的 qsort、Java 的 Arrays.sort()（对基本类型排序）。
归并排序：适合需要稳定性或外排序的场景（如大规模数据无法一次性加载到内存）；如数据库排序、Python 的 sorted() 函数（稳定排序）。

code

// 合并两个已排序的数组
function merge(left, right) {
  let result = [];
  let leftIndex = 0, rightIndex = 0;

  // 比较两个数组的元素，按顺序插入结果数组
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 将剩余元素拼接到结果数组
  return result
    .concat(left.slice(leftIndex))  // 左数组剩余部分
    .concat(right.slice(rightIndex)); // 右数组剩余部分
}

// 归并排序主函数
function mergeSort(arr) {
  // 递归终止条件：数组长度为 0 或 1 时直接返回
  if (arr.length <= 1) {
    return arr;
  }

  // 分割数组
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);  // 左半部分（不包含 mid）
  const right = arr.slice(mid);    // 右半部分（包含 mid）

  // 递归排序并合并
  return merge(
    mergeSort(left),  // 递归排序左半部分
    mergeSort(right)  // 递归排序右半部分
  );
}

// 示例测试
console.log(mergeSort([3, 1, 4, 2]));        // 输出: [1, 2, 3, 4]
console.log(mergeSort([5, 3, 5, 2, 7, 2])); // 输出: [2, 2, 3, 5, 5, 7]
console.log(mergeSort([-3, 0, 10, -2]));    // 输出: [-3, -2, 0, 10]
console.log(mergeSort([]));                 // 输出: []
console.log(mergeSort([1]));                // 输出: [1]

总结

特性	快速排序	归并排序
分治策略	先分区后递归	先递归后合并
额外空间	O(log n)（递归栈）	O(n)（合并数组）
稳定性	不稳定	稳定
最坏时间复杂度	O(n²)	O(n log n)
适用场景	内存排序、随机数据	外排序、稳定性要求

• 选择快速排序：追求实际运行速度，内存有限，且不要求稳定性。
• 选择归并排序：需要稳定性、处理外排序，或接受额外空间开销。