快速排序的实现

问题

快速排序（Quick Sort）是一种高效的排序算法，采用分治法策略。需要实现一个快速排序函数，能够对数组进行原地排序或返回新的排序数组。快速排序的思想是：选择一个基准元素，将数组分为两部分，左边都小于基准，右边都大于基准，然后递归地对两部分进行排序。

解答

/**
 * 快速排序 - 原地排序版本
 * @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;
}

/**
 * 分区函数 - 将数组分为小于和大于基准值的两部分
 * @param {number[]} arr - 数组
 * @param {number} left - 左边界
 * @param {number} right - 右边界
 * @return {number} 基准值最终位置
 */
function partition(arr, left, right) {
  // 选择最右边的元素作为基准值
  const pivot = arr[right];
  // i 指向小于基准值区域的最后一个元素
  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;
}

/**
 * 快速排序 - 非原地排序版本（更易理解）
 * @param {number[]} arr - 待排序数组
 * @return {number[]} 新的排序后数组
 */
function quickSortSimple(arr) {
  // 递归终止条件
  if (arr.length <= 1) {
    return arr;
  }
  
  // 选择中间元素作为基准值
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];
  
  // 分成三部分：小于、等于、大于基准值
  const left = [];
  const middle = [];
  const right = [];
  
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] === pivot) {
      middle.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  // 递归排序并合并
  return [...quickSortSimple(left), ...middle, ...quickSortSimple(right)];
}

使用示例

// 示例1：基本使用
const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log('原数组:', arr1);
quickSort(arr1);
console.log('排序后:', arr1);
// 输出: [11, 12, 22, 25, 34, 64, 90]

// 示例2：使用非原地排序版本
const arr2 = [5, 2, 9, 1, 7, 6, 3];
const sorted = quickSortSimple(arr2);
console.log('原数组:', arr2); // [5, 2, 9, 1, 7, 6, 3] 不变
console.log('排序后:', sorted); // [1, 2, 3, 5, 6, 7, 9]

// 示例3：包含重复元素
const arr3 = [3, 1, 4, 1, 5, 9, 2, 6, 5];
quickSort(arr3);
console.log('排序后:', arr3);
// 输出: [1, 1, 2, 3, 4, 5, 5, 6, 9]

// 示例4：已排序数组
const arr4 = [1, 2, 3, 4, 5];
quickSort(arr4);
console.log('排序后:', arr4);
// 输出: [1, 2, 3, 4, 5]

// 示例5：倒序数组
const arr5 = [5, 4, 3, 2, 1];
quickSort(arr5);
console.log('排序后:', arr5);
// 输出: [1, 2, 3, 4, 5]

关键点

• 分治思想：将大问题分解为小问题，递归解决后合并结果，这是快速排序的思想

• 基准值选择：可以选择第一个、最后一个、中间或随机元素作为基准值，不同选择影响算法性能

• 分区操作：通过一次遍历将数组分为两部分，左边小于基准值，右边大于基准值，这是算法的关键步骤

• 原地排序：通过交换元素实现原地排序，空间复杂度为 O(log n)（递归栈空间）

• 时间复杂度：

  • 平均情况：O(n log n)
  • 最坏情况：O(n²)（数组已排序或逆序时）
  • 最好情况：O(n log n)

• 不稳定排序：相同元素的相对位置可能会改变

• 优化技巧：

  • 三数取中法选择基准值
  • 小数组使用插入排序
  • 尾递归优化减少栈空间