递归实现快速排序js

递归实现快速排序的JavaScript代码

快速排序是一种分治算法，通过递归将数组分成较小的子数组进行排序。以下是JavaScript实现：

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

代码解析

递归基例处理：当数组长度小于等于1时直接返回，因为单元素数组已经是有序的。

选择基准值(pivot)：这里选择数组中间位置的元素作为基准值。

分区操作：创建三个临时数组，分别存放小于、等于和大于基准值的元素。

递归调用：对左右两个子数组递归调用quickSort，并将结果与等于基准值的数组合并。

优化版本（原地排序）

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

时间复杂度分析

最佳情况：O(n log n) - 每次都能均匀划分数组 最差情况：O(n²) - 每次划分都极度不平衡 平均情况：O(n log n)

使用示例

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