排序算法专题

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

📊 算法总览

算法	平均时间	最坏时间	空间	稳定性	适用场景
快速排序	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. 快速排序

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

题目描述

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

核心思路

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

代码实现

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;
}

/**
 * 快速排序 - 非原地版（易理解）
 */
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([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]));
// [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

// 逆序（最坏情况）
console.log(quickSort([5, 4, 3, 2, 1])); // [1, 2, 3, 4, 5]

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

复杂度分析

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

2. 归并排序

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

题目描述

实现归并排序算法。

核心思路

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

代码实现

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++];
  }
  // 右边剩余的已经在正确位置，无需复制
}

示例调用

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([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]

复杂度分析

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

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([3, 1, 4, 1, 5, 9, 2, 6]));
// [1, 1, 2, 3, 4, 5, 6, 9]

// 找第 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;
}

示例调用

javascript

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

// 已排序（最优情况）
console.log(insertionSort([1, 2, 3])); // [1, 2, 3]

// 逆序（最差情况）
console.log(insertionSort([3, 2, 1])); // [1, 2, 3]

复杂度分析

时间: 平均 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

排序算法专题 ​

📊 算法总览 ​

1. 快速排序 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

2. 归并排序 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

3. 堆排序 ​

题目描述 ​

核心思路 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

4. 插入排序 ​

题目描述 ​

代码实现 ​

示例调用 ​

复杂度分析 ​

5. 冒泡排序 ​

代码实现 ​

示例调用 ​

6. 选择排序 ​

代码实现 ​

示例调用 ​

💡 排序算法总结 ​

如何选择排序算法 ​

JavaScript 内置 sort ​

面试高频问题 ​

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

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

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

Q4: 堆排序的优势？ ​

稳定性说明 ​

排序算法专题

📊 算法总览

1. 快速排序

题目描述

核心思路

代码实现

示例调用

复杂度分析

2. 归并排序

题目描述

核心思路

代码实现

示例调用

复杂度分析

3. 堆排序

题目描述

核心思路

代码实现

示例调用

复杂度分析

4. 插入排序

题目描述

代码实现

示例调用

复杂度分析

5. 冒泡排序

代码实现

示例调用

6. 选择排序

代码实现

示例调用

💡 排序算法总结

如何选择排序算法

JavaScript 内置 sort

面试高频问题

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

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

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

Q4: 堆排序的优势？

稳定性说明