javascript

排序与搜索算法

By AI-Writer 15 min read

排序与搜索是算法面试和日常工程中的核心技能。本章手写三种经典排序算法，深入理解分治思想，并掌握复杂度分析方法。

算法复杂度基础

大 O 表示法

大 O 描述的是算法运行时间随输入规模增长的趋势：

复杂度名称示例
O(1)常数数组索引访问
O(log n)对数二分搜索
O(n)线性数组遍历
O(n log n)线性对数快速排序（平均）
O(n²)平方冒泡排序
O(2ⁿ)指数递归斐波那契

复杂度分析忽略常数和低阶项，关注的是数据量趋近无穷时的增长趋势。

时间 vs 空间复杂度

  • 时间复杂度：执行步骤的数量级
  • 空间复杂度：额外占用内存的数量级（不包括输入本身）

归并排序（Merge Sort）

核心思想

分治策略的经典应用：将数组分成两半，分别排序后合并。

javascript
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) {
  const 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), right.slice(j));
}

console.log(mergeSort([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]

复杂度分析

  • 时间复杂度：始终为 O(n log n)。每层递归处理 n 个元素，共 log n 层。
  • 空间复杂度：O(n)。合并时需要额外数组，递归栈深度为 O(log n)。
  • 稳定性：稳定排序。相等元素在合并时保持左半部分在前。

快速排序（Quick Sort）

核心思想

选择一个基准值（pivot），将数组分为”小于 pivot”和”大于 pivot”的两部分，递归处理。

javascript
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  // 选择基准值（这里选中间元素，避免已排序数组的最坏情况）
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const middle = [];
  const right = [];

  for (const num of arr) {
    if (num < pivot) left.push(num);
    else if (num > pivot) right.push(num);
    else middle.push(num);
  }

  return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log(quickSort([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]

原地快排（优化空间）

上面的实现需要额外数组，以下是经典的原地分区版本：

javascript
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;

  const pivotIndex = partition(arr, left, right);
  quickSortInPlace(arr, left, pivotIndex - 1);
  quickSortInPlace(arr, pivotIndex + 1, right);
}

function partition(arr, left, right) {
  // 选最右元素作为 pivot
  const pivot = arr[right];
  let i = left - 1; // i 指向小于 pivot 的最后一个元素

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
    }
  }

  // 将 pivot 放到正确位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

const nums = [3, 1, 4, 1, 5, 9, 2, 6];
quickSortInPlace(nums);
console.log(nums); // [1, 1, 2, 3, 4, 5, 6, 9]

复杂度分析

  • 时间复杂度：平均 O(n log n)，最坏 O(n²)（pivot 每次都选到最大/最小值）
  • 空间复杂度：O(log n) —— 递归栈深度
  • 稳定性：不稳定排序。交换操作可能改变相等元素的相对顺序

随机化 pivot

避免最坏情况的关键是随机选择 pivot：

javascript
function partitionRandom(arr, left, right) {
  const randomIndex = left + Math.floor(Math.random() * (right - left + 1));
  [arr[randomIndex], arr[right]] = [arr[right], arr[randomIndex]];
  return partition(arr, left, right); // 复用之前的 partition 逻辑
}

堆排序（Heap Sort）

核心思想

利用二叉堆的性质：父节点总是大于（最大堆）或小于（最小堆）子节点。

javascript
function heapSort(arr) {
  const n = arr.length;

  // 1. 构建最大堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 2. 逐个将堆顶（最大值）放到数组末尾
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 最大值归位
    heapify(arr, i, 0); // 对剩余元素重新堆化
  }

  return arr;
}

function heapify(arr, size, root) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest); // 递归调整受影响子树
  }
}

console.log(heapSort([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]

复杂度分析

  • 时间复杂度：始终 O(n log n)。建堆 O(n)，每次堆化 O(log n)，共 n 次。
  • 空间复杂度：O(1) —— 原地排序，无需额外数组
  • 稳定性：不稳定排序

三种排序对比

算法平均时间最坏时间空间稳定性适用场景
归并排序O(n log n)O(n log n)O(n)稳定链表排序、需要稳定时
快速排序O(n log n)O(n²)O(log n)不稳定通用场景，平均最快
堆排序O(n log n)O(n log n)O(1)不稳定内存敏感、Top K 问题

基础实现

在已排序数组中以 O(log n) 时间查找目标值：

javascript
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // 未找到
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4)); // -1

使用 left + Math.floor((right - left) / 2) 而非 (left + right) / 2，避免大数溢出。

查找边界

javascript
// 查找第一个大于等于 target 的位置（lower bound）
function lowerBound(arr, target) {
  let left = 0, right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }

  return left; // 返回插入位置
}

console.log(lowerBound([1, 3, 3, 5, 7], 3)); // 1（第一个 3）
console.log(lowerBound([1, 3, 3, 5, 7], 4)); // 3（应插入到 5 的位置）

二分搜索的应用场景

javascript
// 1. 判断是否存在（基础用法）
// 2. 查找插入位置（lower/upper bound）
// 3. 查找旋转排序数组的最小值
function findMinInRotated(arr) {
  let left = 0, right = arr.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] > arr[right]) left = mid + 1; // 最小值在右半部分
    else right = mid; // arr[mid] < arr[right]，最小值在左半部分或就是 mid
  }

  return arr[left];
}

console.log(findMinInRotated([4, 5, 6, 7, 0, 1, 2])); // 0

Top K 问题

使用最小堆高效解决”查找数组中最大的 K 个元素”：

javascript
function topK(nums, k) {
  // 维护一个大小为 k 的最小堆
  // 注：MinPriorityQueue 需引入外部库（如 @datastructures-js/priority-queue）
  const minHeap = new MinPriorityQueue();

  for (const num of nums) {
    minHeap.enqueue(num);
    if (minHeap.size() > k) {
      minHeap.dequeue(); // 移除最小值，保留前 k 大
    }
  }

  return minHeap.toArray();
}

// 时间复杂度：O(n log k) —— 远优于全排序的 O(n log n)

小结

  • 归并排序：分治 + 合并，稳定但需 O(n) 额外空间
  • 快速排序：分治 + 分区，平均最快但不稳定，随机 pivot 防退化
  • 堆排序：完全二叉堆性质，原地排序 O(1) 空间，不稳定
  • 二分搜索：仅适用于有序数据，O(log n)，注意边界条件
  • 复杂度分析：关注增长趋势，常数和低阶项可忽略

掌握这些算法的核心思想，比死记硬背代码更重要。分治、递归、堆化——这些模式会反复出现在各种算法问题中。

#javascript #algorithm #排序 #搜索 #复杂度分析

评论

A

Written by

AI-Writer

Related Articles

javascript
#11

数组内置方法综合运用

深入掌握 forEach、map、filter、reduce、find、sort 等数组方法的组合技巧，避开常见性能陷阱，写出更高效的函数式代码。

Read More
Back to All Articles