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 (let 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)];
}

优化原地排序版本

原地排序版本减少了空间复杂度，直接在原数组上进行操作：

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

时间复杂度分析

• 最佳情况：O(n log n)，每次划分都能将数组均匀分成两部分。
• 最坏情况：O(n²)，当数组已经有序或逆序时，每次划分只能减少一个元素。
• 平均情况：O(n log n)。

使用注意事项

• 对于小规模数组（如长度 < 10），插入排序可能更高效，可结合使用。
• 基准选择策略影响性能，常见方法包括随机选择、三数取中等。
• 递归实现可能引发栈溢出，对于大规模数据建议使用尾递归优化或迭代实现。