前端面试知识库

Appearance

排序算法专题 ​

排序是算法基础，重点掌握 快速排序、归并排序、堆排序

📊 算法总览 ​

算法平均时间最坏时间空间稳定性适用场景
快速排序O(n log n)O(n²)O(log n)不稳定通用、大数据量
归并排序O(n log n)O(n log n)O(n)稳定链表、外部排序
堆排序O(n log n)O(n log n)O(1)不稳定内存受限
冒泡排序O(n²)O(n²)O(1)稳定小数据、教学
插入排序O(n²)O(n²)O(1)稳定小数据、近乎有序
选择排序O(n²)O(n²)O(1)不稳定小数据

1. 快速排序 ​

难度: ⭐⭐⭐ | 梯队: 第一梯队 ✅ | 标签: 分治, 递归

题目描述 ​

实现快速排序算法，对数组进行原地排序。

核心思路 ​

  1. 选择一个基准元素（pivot）
  2. 将数组分为两部分：小于 pivot 的放左边，大于的放右边
  3. 递归对左右两部分排序

代码实现 ​

javascript
/**
 * 快速排序 - 原地排序版（推荐）
 * @param {number[]} arr
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

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

  return arr;
}

/**
 * 分区函数 - Lomuto 分区方案
 */
function partition(arr, left, right) {
  const pivot = arr[right]; // 选择最后一个作为基准
  let i = left;

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

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

/**
 * 快速排序 - 三数取中优化
 * 避免最坏情况 O(n²)
 */
function quickSortOptimized(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  // 三数取中
  const mid = Math.floor((left + right) / 2);
  if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
  if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
  if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
  // 现在 arr[mid] 是中间值，将其移到 right-1 位置
  [arr[mid], arr[right - 1]] = [arr[right - 1], arr[mid]];

  if (right - left <= 2) return arr; // 小于等于 3 个元素已排好

  const pivot = arr[right - 1];
  let i = left;
  let j = right - 1;

  while (true) {
    while (arr[++i] < pivot) {}
    while (arr[--j] > pivot) {}
    if (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    } else {
      break;
    }
  }

  [arr[i], arr[right - 1]] = [arr[right - 1], arr[i]];

  quickSortOptimized(arr, left, i - 1);
  quickSortOptimized(arr, i + 1, right);

  return arr;
}

/**
 * 快速排序 - 非原地版（易理解）
 */
function quickSortSimple(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 [...quickSortSimple(left), ...middle, ...quickSortSimple(right)];
}

示例调用 ​

javascript
// 基础示例
console.log(quickSort([5, 3, 7, 2, 8, 4, 1, 9, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

// 边界条件：空数组
console.log(quickSort([])); // []

// 边界条件：单元素
console.log(quickSort([1])); // [1]

// 边界条件：两个元素
console.log(quickSort([2, 1])); // [1, 2]

// 边界条件：已排序数组
console.log(quickSort([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

// 边界条件：逆序数组（最坏情况）
console.log(quickSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5]

// 边界条件：有重复元素
console.log(quickSort([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]));
// [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

// 边界条件：全部相同
console.log(quickSort([5, 5, 5, 5])); // [5, 5, 5, 5]

// 边界条件：包含负数
console.log(quickSort([-3, 0, 5, -1, 2])); // [-3, -1, 0, 2, 5]

// 边界条件：大数组
const largeArr = Array.from({ length: 10000 }, () => Math.random());
console.log(quickSort([...largeArr]).length); // 10000

复杂度分析 ​

  • 时间: 平均 O(n log n)，最坏 O(n²)
  • 空间: O(log n) 递归栈

2. 归并排序 ​

难度: ⭐⭐⭐ | 梯队: 第一梯队 ✅ | 标签: 分治, 稳定排序

题目描述 ​

实现归并排序算法。

核心思路 ​

  1. 将数组递归地分成两半
  2. 对每半进行排序
  3. 合并两个有序数组

代码实现 ​

javascript
/**
 * 归并排序 - 标准版
 * @param {number[]} arr
 * @return {number[]}
 */
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)).concat(right.slice(j));
}

/**
 * 归并排序 - 原地版（减少空间开销）
 */
function mergeSortInPlace(arr, temp = [], left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  const mid = Math.floor((left + right) / 2);
  mergeSortInPlace(arr, temp, left, mid);
  mergeSortInPlace(arr, temp, mid + 1, right);
  mergeInPlace(arr, temp, left, mid, right);

  return arr;
}

function mergeInPlace(arr, temp, left, mid, right) {
  // 复制到临时数组
  for (let i = left; i <= right; i++) {
    temp[i] = arr[i];
  }

  let i = left, j = mid + 1, k = left;

  while (i <= mid && j <= right) {
    if (temp[i] <= temp[j]) {
      arr[k++] = temp[i++];
    } else {
      arr[k++] = temp[j++];
    }
  }

  while (i <= mid) {
    arr[k++] = temp[i++];
  }
  // 右边剩余的已经在正确位置，无需复制
}

/**
 * 归并排序 - 迭代版（自底向上）
 */
function mergeSortIterative(arr) {
  const n = arr.length;
  const temp = new Array(n);

  for (let size = 1; size < n; size *= 2) {
    for (let left = 0; left < n - size; left += 2 * size) {
      const mid = left + size - 1;
      const right = Math.min(left + 2 * size - 1, n - 1);
      mergeInPlace(arr, temp, left, mid, right);
    }
  }

  return arr;
}

示例调用 ​

javascript
// 基础示例
console.log(mergeSort([5, 3, 7, 2, 8, 4, 1, 9, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

// 边界条件：空数组
console.log(mergeSort([])); // []

// 边界条件：单元素
console.log(mergeSort([1])); // [1]

// 边界条件：已排序
console.log(mergeSort([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

// 边界条件：逆序
console.log(mergeSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5]

// 边界条件：有重复（稳定排序验证）
const withDuplicates = [
  { val: 3, id: 1 },
  { val: 1, id: 2 },
  { val: 3, id: 3 },
  { val: 2, id: 4 }
];
// 归并排序会保持相同值的相对顺序

// 边界条件：奇数个元素
console.log(mergeSort([3, 1, 4, 1, 5])); // [1, 1, 3, 4, 5]

// 边界条件：负数
console.log(mergeSort([-5, 3, -2, 0, 1])); // [-5, -2, 0, 1, 3]

// 原地版
console.log(mergeSortInPlace([5, 3, 7, 2, 8]));
// [2, 3, 5, 7, 8]

// 迭代版
console.log(mergeSortIterative([5, 3, 7, 2, 8]));
// [2, 3, 5, 7, 8]

复杂度分析 ​

  • 时间: O(n log n)（最好、最坏、平均都相同）
  • 空间: O(n)

3. 堆排序 ​

难度: ⭐⭐⭐ | 梯队: 第二梯队 | 标签: 堆, 原地排序

题目描述 ​

使用堆数据结构实现排序算法。

核心思路 ​

  1. 建立最大堆
  2. 将堆顶（最大值）与末尾交换
  3. 调整堆，重复直到排序完成

代码实现 ​

javascript
/**
 * 堆排序
 * @param {number[]} arr
 * @return {number[]}
 */
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;
}

/**
 * 调整堆 - 将以 i 为根的子树调整为最大堆
 * @param {number[]} arr - 数组
 * @param {number} n - 堆的大小
 * @param {number} i - 要调整的节点索引
 */
function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

/**
 * 堆排序 - 迭代版 heapify
 */
function heapifyIterative(arr, n, i) {
  while (true) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

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

    if (largest === i) break;

    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

/**
 * 找第 K 大元素（堆排序的应用）
 */
function findKthLargest(nums, k) {
  const n = nums.length;

  // 建堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(nums, n, i);
  }

  // 取出前 k-1 个最大值
  for (let i = n - 1; i > n - k; i--) {
    [nums[0], nums[i]] = [nums[i], nums[0]];
    heapify(nums, i, 0);
  }

  return nums[0];
}

示例调用 ​

javascript
// 基础示例
console.log(heapSort([5, 3, 7, 2, 8, 4, 1, 9, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

// 边界条件：空数组
console.log(heapSort([])); // []

// 边界条件：单元素
console.log(heapSort([1])); // [1]

// 边界条件：两个元素
console.log(heapSort([2, 1])); // [1, 2]

// 边界条件：已排序
console.log(heapSort([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

// 边界条件：逆序
console.log(heapSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5]

// 边界条件：有重复
console.log(heapSort([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]

// 边界条件：负数
console.log(heapSort([-3, 5, 0, -1, 2])); // [-3, -1, 0, 2, 5]

// 找第 K 大
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

复杂度分析 ​

  • 时间: O(n log n)
  • 空间: O(1)（原地排序）

4. 插入排序 ​

难度: ⭐⭐ | 梯队: 基础 | 标签: 稳定排序

题目描述 ​

实现插入排序算法，适合小规模或近乎有序的数据。

代码实现 ​

javascript
/**
 * 插入排序
 * @param {number[]} arr
 * @return {number[]}
 */
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;

    // 将大于 key 的元素后移
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}

/**
 * 二分插入排序
 * 使用二分查找减少比较次数
 */
function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let left = 0, right = i - 1;

    // 二分查找插入位置
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] > key) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    // 后移元素
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }

    arr[left] = key;
  }

  return arr;
}

示例调用 ​

javascript
// 基础示例
console.log(insertionSort([5, 3, 7, 2, 8])); // [2, 3, 5, 7, 8]

// 边界条件
console.log(insertionSort([]));           // []
console.log(insertionSort([1]));          // [1]
console.log(insertionSort([2, 1]));       // [1, 2]
console.log(insertionSort([1, 2, 3]));    // [1, 2, 3] (已排序，最优)
console.log(insertionSort([3, 2, 1]));    // [1, 2, 3] (逆序，最差)

// 二分插入排序
console.log(binaryInsertionSort([5, 3, 7, 2, 8])); // [2, 3, 5, 7, 8]

复杂度分析 ​

  • 时间: 平均 O(n²)，最好 O(n)（已排序）
  • 空间: O(1)

5. 冒泡排序 ​

难度: ⭐ | 梯队: 基础 | 标签: 稳定排序

代码实现 ​

javascript
/**
 * 冒泡排序
 * @param {number[]} arr
 * @return {number[]}
 */
function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // 优化：如果没有交换，说明已经有序
    if (!swapped) break;
  }

  return arr;
}

示例调用 ​

javascript
console.log(bubbleSort([5, 3, 7, 2, 8])); // [2, 3, 5, 7, 8]
console.log(bubbleSort([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5] (提前退出)
console.log(bubbleSort([]));              // []
console.log(bubbleSort([1]));             // [1]

6. 选择排序 ​

难度: ⭐ | 梯队: 基础 | 标签: 不稳定排序

代码实现 ​

javascript
/**
 * 选择排序
 * @param {number[]} arr
 * @return {number[]}
 */
function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

示例调用 ​

javascript
console.log(selectionSort([5, 3, 7, 2, 8])); // [2, 3, 5, 7, 8]
console.log(selectionSort([]));              // []
console.log(selectionSort([1]));             // [1]

💡 排序算法总结 ​

如何选择排序算法 ​

1. 小数据量（n < 50）→ 插入排序
2. 大数据量 + 不要求稳定 → 快速排序
3. 大数据量 + 要求稳定 → 归并排序
4. 内存受限 → 堆排序
5. 链表排序 → 归并排序
6. 近乎有序 → 插入排序
7. 外部排序 → 归并排序

JavaScript 内置 sort ​

javascript
// V8 引擎使用 TimSort（归并 + 插入排序的混合）
// 稳定排序，最坏 O(n log n)

// 注意：默认按字符串排序！
[10, 2, 1].sort();        // [1, 10, 2] ❌
[10, 2, 1].sort((a, b) => a - b); // [1, 2, 10] ✅

面试高频问题 ​

Q1: 快排最坏情况如何避免？ ​

使用随机选择基准或三数取中法，避免有序数组的 O(n²) 情况。

Q2: 什么时候用归并排序？ ​

  • 需要稳定排序
  • 链表排序（不需要额外空间）
  • 外部排序（数据量大于内存）

Q3: 为什么快排比归并排序快？ ​

  • 快排的常数因子更小
  • 快排是原地排序，缓存命中率更高
  • 归并需要额外空间，有内存分配开销

Q4: 堆排序的优势？ ​

  • 空间复杂度 O(1)
  • 最坏情况也是 O(n log n)
  • 适合找 Top K 问题

稳定性说明 ​

javascript
// 稳定排序：相同元素的相对顺序不变
const arr = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 20 }
];

// 按 age 排序后，Alice 和 Bob（都是 25 岁）的顺序：
// 稳定排序：Alice, Bob（保持原顺序）
// 不稳定排序：可能是 Bob, Alice

代码模板 ​

javascript
// 快速排序核心：分区
function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// 归并排序核心：合并
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

// 堆排序核心：下沉
function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1, right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

前端面试知识库

Copyright © 2026