当前位置：首页 > JavaScript

js快速排序的实现

2026-01-30 16:15:20JavaScript

快速排序的基本原理

快速排序是一种高效的排序算法，采用分治策略。通过选择一个基准元素（pivot），将数组分为两部分：小于基准的元素和大于基准的元素。递归地对这两部分进行排序，最终合并得到有序数组。

实现步骤

选择基准（pivot） 通常选择数组的第一个、最后一个或中间元素作为基准。以下实现以数组中间元素为例。

js快速排序的实现

分区操作 遍历数组，将小于基准的元素移到基准左侧，大于基准的元素移到右侧。分区完成后，基准元素处于正确的位置。

递归排序 对基准左侧和右侧的子数组递归调用快速排序，直到子数组长度为1或0时终止。

js快速排序的实现

代码实现

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

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

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

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

// 示例用法
const array = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quickSort(array);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]

优化点

原地排序（节省空间） 通过交换元素实现原地分区，避免创建临时数组。以下是原地排序的实现：

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

// 示例用法
const array = [3, 6, 8, 10, 1, 2, 1];
quickSortInPlace(array);
console.log(array); // 输出: [1, 1, 2, 3, 6, 8, 10]

基准选择优化 为避免最坏情况（如数组已有序），可采用随机选择基准或三数取中法（选择左、中、右三个元素的中位数）。