快速排序算法实现

/**
 * 快速排序算法实现
 * 时间复杂度: 平均 O(n log n)，最坏 O(n²)
 * 空间复杂度: O(log n)
 * @param {Array} arr - 待排序数组
 * @returns {Array} 排序后的数组
 */
function quickSort(arr) {
  // 基线条件：数组长度为0或1时直接返回
  if (arr.length <= 1) return arr;
  
  // 选择基准值（这里选择最后一个元素）
  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];
  
  // 分区操作：将小于基准值的元素放到left数组，大于等于基准值的元素放到right数组
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  // 递归地对左右子数组进行快速排序，然后合并结果
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 原地快速排序实现（更高效）
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);
  
  return arr;
}

// 分区函数
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;
}

// 示例使用
console.log('快速排序示例:');
const unsortedArray = [9, 2, 7, 4, 5, 8, 1, 6, 3];
console.log('原始数组:', unsortedArray);
console.log('排序结果:', quickSort(unsortedArray));

// 测试原地排序
const arr2 = [64, 34, 25, 12, 22, 11, 90];
console.log('原地排序前:', arr2);
quickSortInPlace(arr2);
console.log('原地排序后:', arr2);