# 快速排序（Quick Sort）

URL: https://caijiao.org/sort/6-quick-sort
Source: docs/sort/6-quick-sort.md
Description: 讲解快速排序的分治思想与实现步骤，适合处理大规模数据，附带 JavaScript、Python、C++、Java、PHP、Go 多语言代码及详细说明

快速排序是应用最广泛的排序算法之一，采用**分治法（Divide and Conquer）**策略：每次选择一个“基准元素”将数组划分为左右两部分，然后递归排序左右两侧子数组。

由于其平均时间复杂度为 O(n log n)、原地排序、常数因子小，在大多数实际应用中性能优于归并排序与堆排序。

## 📌 算法原理解释

快速排序的核心流程如下：

1. **选定一个基准（pivot）**，通常是当前子数组的第一个、最后一个或中间值；
2. 将数组划分为两部分：小于等于基准值的放左边，大于的放右边；
3. 对左右两部分分别递归执行快速排序；
4. 最终组合结果。

例如数组 `[6, 3, 8, 5, 2]`，以 `6` 为基准：

- 小于6的：[3, 5, 2]
- 大于6的：[8]
- 合并为 `[2, 3, 5, 6, 8]`

## 💻 多语言代码实现


// JavaScript 快速排序
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x > pivot);

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

```python
# Python 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)
```

```cpp
// C++ 快速排序（原地）
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left], i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}
```

```java
// Java 快速排序
public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[left], i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}
```

```php
<?php
// PHP 快速排序
function quickSort(array $arr): array {
    if (count($arr) <= 1) return $arr;

    $pivot = $arr[0];
    $left = array_filter(array_slice($arr, 1), fn($x) => $x <= $pivot);
    $right = array_filter(array_slice($arr, 1), fn($x) => $x > $pivot);

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}
?>
```

```go
// Go 快速排序
package main

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[0]
    left, right := []int{}, []int{}
    for _, v := range arr[1:] {
        if v <= pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    left = quickSort(left)
    right = quickSort(right)
    return append(append(left, pivot), right...)
}
```


## ✅ 算法特点与总结

| 属性     | 描述                             |
| ------ | ------------------------------ |
| 时间复杂度  | 平均 O(n log n)，最坏 O(n²)（已排序时最差） |
| 空间复杂度  | O(log n)（递归栈）或 O(n)（函数式写法）     |
| 稳定性    | ❌ 不稳定                          |
| 是否原地排序 | ✅ 可实现原地排序（如 C++/Java 实现）       |

> ⚠️ 提示：快速排序虽然最坏时间复杂度是 O(n²)，但在实际中非常高效，建议搭配“三数取中”或随机基准优化其稳定性。