如何用JavaScript实现快速排序算法？

快速排序是一种采用分治思想的高效排序算法，平均时间复杂度为O(n log n)，在很多场景下比冒泡排序、选择排序等基础排序算法性能更好，是JavaScript开发中处理数组排序的常用方案。

快速排序的核心逻辑

快速排序的整个流程可以分为三个核心步骤：

• 选取基准值：从待排序的数组中挑选一个元素作为基准，通常可以选择数组的第一个、最后一个或者中间的元素。
• 分区操作：遍历数组，把所有小于基准值的元素放到基准左侧，大于基准值的元素放到基准右侧，基准值最终会处于它正确的排序位置。
• 递归排序：对基准值左侧和右侧的两个子数组分别重复上述两个步骤，直到所有子数组的长度都为1，整个数组就完成了排序。

基础版JavaScript实现

下面是最直观的递归实现方式，逻辑和上述核心步骤完全对应：

// 快速排序基础实现
function quickSort(arr) {
  // 如果数组长度小于等于1，直接返回，不需要排序
  if (arr.length <= 1) {
    return arr;
  }
  // 选取数组中间的元素作为基准值
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];
  // 定义存放小于、等于、大于基准值的数组
  const left = [];
  const equal = [];
  const right = [];
  // 遍历数组进行分区
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] === pivot) {
      equal.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 递归处理左右子数组，拼接结果
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

// 测试示例
const testArr = [3, 6, 8, 2, 1, 9, 5, 4, 7];
console.log('排序前：', testArr);
console.log('排序后：', quickSort(testArr));

原地排序优化版本

上面的基础版本会创建多个新数组，占用额外的内存空间，我们可以优化为原地排序的版本，减少空间开销：

// 原地快速排序实现
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) {
    return arr;
  }
  // 分区函数，返回基准值最终的位置
  function partition(left, right) {
    // 选取最右侧元素作为基准值
    const pivot = arr[right];
    let i = left - 1;
    for (let j = left; j < right; j++) {
      // 如果当前元素小于基准值，交换到左侧区域
      if (arr[j] <= pivot) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    // 把基准值放到正确的位置
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
  }
  const pivotIndex = partition(left, right);
  // 递归处理左右子数组
  quickSortInPlace(arr, left, pivotIndex - 1);
  quickSortInPlace(arr, pivotIndex + 1, right);
  return arr;
}

// 测试示例
const testArr2 = [10, 3, 7, 1, 9, 2, 8, 5, 6, 4];
console.log('排序前：', testArr2);
console.log('排序后：', quickSortInPlace(testArr2));

算法复杂度分析

快速排序的性能表现和基准值的选择有很大关系：

• 平均时间复杂度：O(n log n)，是效率很高的排序算法。
• 最坏时间复杂度：O(n²)，当每次选取的基准值都是数组的最大或最小元素时会出现，比如已经有序的数组用第一个元素作为基准就会触发这种情况。
• 空间复杂度：基础版本因为创建了新数组，空间复杂度为O(n)；原地排序版本如果忽略递归栈的开销，空间复杂度可以降到O(log n)。

实际开发优化建议

为了避免最坏情况的出现，实际使用时可以做一些优化：

• 基准值选择：不要固定选第一个或最后一个元素，可以随机选取数组中的一个元素作为基准，或者取左、中、右三个元素的中间值作为基准。
• 小数组优化：当子数组的长度小于10的时候，可以改用插入排序，因为小数组场景下插入排序的性能比快速排序更好。
• 尾递归优化：部分JavaScript引擎支持尾递归优化，调整递归的顺序可以减少递归栈的深度，避免栈溢出。

另外需要注意，JavaScript内置的Array.prototype.sort()方法在大部分现代引擎中对于大数组已经采用了类似快速排序的优化实现，如果是普通业务场景不需要自己实现排序，但理解快速排序的实现逻辑对于算法学习和面试都很有帮助。

JavaScript快速排序算法实现排序算法修改时间：2026-06-05 02:11:34