力扣鏈接912. 排序數(shù)組 - 力扣（LeetCode）注意這題快排不能用遞歸，否則堆會(huì)爆

快速排序（Quicksort）是一種高效的排序算法，通常使用分治法來將一個(gè)列表分成較小的子列表，然后遞歸地排序這些子列表。以下是用 JavaScript 實(shí)現(xiàn)快速排序的幾種方式：

### 方法一：標(biāo)準(zhǔn)遞歸實(shí)現(xiàn)

```javascript
function quickSort(arr) {
? ? // 如果數(shù)組長度小于等于1，則直接返回（已排序）
? ? if (arr.length <= 1) {
? ? ? ? return arr;
? ? }

? ? // 選擇基準(zhǔn)元素（這里選擇中間元素）
? ? const pivotIndex = Math.floor(arr.length / 2);
? ? const pivot = arr[pivotIndex];

? ? // 定義左右兩個(gè)數(shù)組
? ? const left = [];
? ? const right = [];

? ? // 遍歷數(shù)組（跳過基準(zhǔn)元素），根據(jù)與基準(zhǔn)元素的比較結(jié)果放入left或right
? ? for (let i = 0; i < arr.length; i++) {
? ? ? ? if (i === pivotIndex) continue; // 跳過基準(zhǔn)元素
? ? ? ? if (arr[i] < pivot) {
? ? ? ? ? ? left.push(arr[i]);
? ? ? ? } else {
? ? ? ? ? ? right.push(arr[i]);
? ? ? ? }
? ? }

? ? // 遞歸調(diào)用quickSort并合并結(jié)果
? ? 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）

這種方法不需要額外的空間來存儲(chǔ) `left` 和 `right` 數(shù)組，而是通過交換元素在原數(shù)組上進(jìn)行排序。

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

? ? // 分區(qū)函數(shù)，返回分區(qū)點(diǎn)索引
? ? function partition(arr, left, right) {
? ? ? ? const pivot = arr[right]; // 選擇最右邊的元素作為基準(zhǔn)
? ? ? ? let i = left;

? ? ? ? for (let j = left; j < right; j++) {
? ? ? ? ? ? if (arr[j] <= pivot) {
? ? ? ? ? ? ? ? [arr[i], arr[j]] = [arr[j], arr[i]]; // 交換
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? // 將基準(zhǔn)元素放到正確的位置
? ? ? ? [arr[i], arr[right]] = [arr[right], arr[i]];
? ? ? ? return i;
? ? }

? ? // 獲取分區(qū)點(diǎn)
? ? const pivotIndex = partition(arr, left, right);

? ? // 遞歸對左右兩部分進(jìn)行排序
? ? 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]
```

### 方法三：隨機(jī)化快速排序

為了減少最壞情況的發(fā)生概率（例如當(dāng)輸入已經(jīng)是排序好的數(shù)組時(shí)），可以選擇一個(gè)隨機(jī)的基準(zhǔn)元素來進(jìn)行分區(qū)。

```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]]; // 交換隨機(jī)基準(zhǔn)到末尾

? ? ? ? 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]]; // 將基準(zhǔn)元素放到正確的位置
? ? ? ? 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]
```

這三種方法展示了不同的快速排序?qū)崿F(xiàn)方式。第一種是最簡單的遞歸實(shí)現(xiàn)，第二種是更高效的原地排序，而第三種則是引入了隨機(jī)化以提高性能穩(wěn)定性。你可以根據(jù)具體需求選擇最適合的方法。