三天精通一算法之快速排序

力扣链接912. 排序数组 - 力扣（LeetCode）注意这题快排不能用递归，否则堆会爆

快速排序（Quicksort）是一种高效的排序算法，通常使用分治法来将一个列表分成较小的子列表，然后递归地排序这些子列表。以下是用 JavaScript 实现快速排序的几种方式：

### 方法一：标准递归实现

```javascript
function quickSort(arr) {
    // 如果数组长度小于等于1，则直接返回（已排序）
    if (arr.length <= 1) {
        return arr;
    }

    // 选择基准元素（这里选择中间元素）
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr[pivotIndex];

    // 定义左右两个数组
    const left = [];
    const right = [];

    // 遍历数组（跳过基准元素），根据与基准元素的比较结果放入left或right
    for (let i = 0; i < arr.length; i++) {
        if (i === pivotIndex) continue; // 跳过基准元素
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // 递归调用quickSort并合并结果
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```

### 方法二：原地排序（in-place）

这种方法不需要额外的空间来存储 `left` 和 `right` 数组，而是通过交换元素在原数组上进行排序。

```javascript
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
    if (left >= 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;
    }

    // 获取分区点
    const pivotIndex = partition(arr, left, right);

    // 递归对左右两部分进行排序
    quickSortInPlace(arr, left, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, right);

    return arr;
}

// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortInPlace(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```

### 方法三：随机化快速排序

为了减少最坏情况的发生概率（例如当输入已经是排序好的数组时），可以选择一个随机的基准元素来进行分区。

```javascript
function quickSortRandomized(arr, left = 0, right = arr.length - 1) {
    if (left >= right) {
        return arr;
    }

    function partition(arr, left, right) {
        const randomPivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        [arr[randomPivotIndex], arr[right]] = [arr[right], arr[randomPivotIndex]]; // 交换随机基准到末尾

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

    const pivotIndex = partition(arr, left, right);

    quickSortRandomized(arr, left, pivotIndex - 1);
    quickSortRandomized(arr, pivotIndex + 1, right);

    return arr;
}

// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortRandomized(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```

这三种方法展示了不同的快速排序实现方式。第一种是最简单的递归实现，第二种是更高效的原地排序，而第三种则是引入了随机化以提高性能稳定性。你可以根据具体需求选择最适合的方法。