### 快速排序介绍
**快速排序**是一种基于分治思想的高效排序算法，由 Tony Hoare 在 1960 年提出。其核心步骤如下：
1. **选择基准值（Pivot）**：从数组中随机或按特定策略选取一个元素作为基准。
2. **分区（Partition）**：将数组划分为两部分，左侧元素均小于等于基准值，右侧元素均大于基准值。
3. **递归排序**：对左右子数组递归执行上述步骤，直到子数组长度为 1。
#### 时间复杂度
- **平均情况**：\( O(n \log n) \)
- **最坏情况**：\( O(n^2) \)（可通过随机化避免）
- **空间复杂度**：\( O(\log n) \)（递归栈深度）
---
### C++ 代码实现（随机化基准值）
```cpp
#include
#include
using namespace std;
// 分区函数：随机选择基准值并划分数组
int partition(int arr[], int low, int high) {
// 随机选择基准值并交换到末尾
int random = low + rand() % (high - low + 1);
swap(arr[random], arr[high]);
int pivot = arr[high];
int i = low - 1; // 记录小于基准值的右边界
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // 将基准值放到正确位置
return i + 1;
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区
quickSort(arr, low, pi - 1); // 递归左子数组
quickSort(arr, pi + 1, high); // 递归右子数组
}
}
// 示例
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
---
### 适用场景分析
#### 1. **适合场景**
- **大规模数据**：平均时间复杂度 \( O(n \log n) \)，性能优于大多数排序算法。
- **内存敏感场景**：原地排序，空间复杂度 \( O(\log n) \)。
- **随机分布数据**：随机化基准值避免最坏情况，性能稳定。
#### 2. **不适合场景**
- **已基本有序的数据**：若无随机化基准值，退化为 \( O(n^2) \)。
- **稳定性要求严格**：快速排序是不稳定排序。
- **递归深度受限环境**：递归可能引发栈溢出（可改用迭代实现）。
#### 3. **优化建议**
- **小规模数据**：结合插入排序（如数组长度 ≤ 15 时切换）。
- **三数取中法**：选择中位数作为基准值，进一步避免最坏情况。
---
快速排序凭借其高效性和低内存占用，成为实际应用中最常用的排序算法之一，尤其适用于通用数据排序需求。