快速排序是一种高效的排序算法，基于分治法思想，平均时间复杂度为O(n log n)，在实际应用中非常流行。它的核心是通过选择一个基准元素(pivot)，将数组分为两部分，一部分所有元素小于基准，另一部分所有元素大于基准，然后递归地对这两部分进行排序。
一、快速排序的核心思想¶
- 分治法：将一个大问题分解为多个小问题解决。
- 选择基准：在数组中选择一个元素作为基准(pivot)。
- 分区操作：重新排列数组，使所有小于基准的元素移到基准左侧，大于基准的元素移到右侧。
- 递归排序：递归处理基准左侧和右侧的子数组。
二、分区过程（Lomuto分区方案）¶
以数组最右侧元素作为基准(pivot)，具体步骤：
1. 初始化指针i指向小于基准区域的末尾（初始为left-1）。
2. 遍历数组从left到right-1，若当前元素小于基准，将i右移并交换当前元素到小于区域。
3. 遍历结束后，将基准元素与i+1位置的元素交换，此时基准元素位于最终位置。
三、C++代码实现¶
1. 分区函数（partition）¶
// 分区函数：返回基准元素的最终位置
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right]; // 选择最右侧元素作为基准
int i = left - 1; // 小于基准区域的边界（初始为空）
for (int j = left; j < right; j++) { // 遍历除基准外的所有元素
if (nums[j] < pivot) { // 当前元素小于基准
i++; // 扩展小于区域
swap(nums[i], nums[j]); // 交换到小于区域
}
}
swap(nums[i + 1], nums[right]); // 将基准放到最终位置
return i + 1; // 返回基准位置
}
2. 快速排序主函数（quickSort）¶
// 快速排序主函数：递归排序数组的[left, right]区间
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 基本情况：子数组长度为1或0，无需排序
int pivotIndex = partition(nums, left, right); // 获取基准位置
quickSort(nums, left, pivotIndex - 1); // 递归排序左半部分
quickSort(nums, pivotIndex + 1, right); // 递归排序右半部分
}
3. 测试代码¶
#include <iostream>
#include <vector>
using namespace std;
// 分区函数
int partition(vector<int>& nums, int left, int right) { /* 代码同上 */ }
// 快速排序主函数
void quickSort(vector<int>& nums, int left, int right) { /* 代码同上 */ }
int main() {
vector<int> arr = {6, 3, 8, 5, 2, 7, 1, 4};
int n = arr.size();
cout << "排序前数组：";
for (int num : arr) cout << num << " ";
cout << endl;
quickSort(arr, 0, n - 1); // 调用快速排序
cout << "排序后数组：";
for (int num : arr) cout << num << " ";
cout << endl;
return 0;
}
四、运行结果¶
排序前数组：6 3 8 5 2 7 1 4
排序后数组：1 2 3 4 5 6 7 8
五、关键说明¶
- 原地排序：分区操作在原数组上完成，无需额外空间。
- 递归终止条件：当子数组长度小于等于1时（
left >= right），递归结束。 - 时间复杂度：平均O(n log n)，最坏情况O(n²)（如数组已排序且选最左/右元素为基准），通过随机选基准可优化。
快速排序是面试和实际开发中高频考察的算法，掌握其分区逻辑和递归思想是理解高效排序的关键。通过以上代码和注释，初学者可逐步掌握其实现原理。