请用js实现

以下是用JavaScript实现快速排序的代码示例：

快速排序实现

快速排序是一种分治算法，通过递归地将数组分为较小和较大的子数组来实现排序。

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

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

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

使用示例

const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]

算法分析

• 时间复杂度：平均情况O(n log n)，最坏情况O(n²)
• 空间复杂度：O(log n)（递归调用栈）

优化版本

以下是原地排序的优化版本，减少了空间复杂度：

function quickSortOptimized(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSortOptimized(arr, left, pivotIndex - 1);
    quickSortOptimized(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;
}