快速排序是一种基于分治思想的高效排序算法，平均时间复杂度为O(n log n)，在很多场景下排序性能优于其他基础排序算法，是C++开发中常用的排序实现方案。其核心逻辑是通过选取一个基准值，将数组分为两部分，一部分元素都小于基准值，另一部分都大于基准值，再对两部分分别递归排序，最终得到有序数组。
快速排序的基础实现
基础快速排序的实现分为三个部分：基准值选取、分区操作、递归排序。下面的代码是标准的C++实现示例：
#include <iostream>
#include <vector>
using namespace std;
// 分区函数，选取最后一个元素为基准，返回基准的最终位置
int partition(vector<int>& arr, int low, int 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(vector<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() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "排序后的数组: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
快速排序的常见优化技巧
基础实现的快速排序在极端情况下会出现性能下降，比如数组已经有序时，时间复杂度会退化为O(n²)，可以通过以下技巧优化：
1. 优化基准值选取
基础实现固定选取最后一个元素作为基准，容易在有序数组下出现最坏情况，常用的优化方式是三数取中法，即选取数组首、中、尾三个元素的中间值作为基准，减少最坏情况出现的概率。
// 三数取中法选取基准，返回基准的索引
int medianOfThree(vector<int>& arr, int low, int high) {
int mid = low + (high - low) / 2;
// 排序三个位置的元素，返回中间值的索引
if (arr[mid] < arr[low]) swap(arr[mid], arr[low]);
if (arr[high] < arr[low]) swap(arr[high], arr[low]);
if (arr[high] < arr[mid]) swap(arr[high], arr[mid]);
return mid;
}
// 优化后的分区函数，使用三数取中法选基准
int optimizedPartition(vector<int>& arr, int low, int high) {
int pivotIndex = medianOfThree(arr, low, high);
swap(arr[pivotIndex], 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;
}
2. 小数组切换为插入排序
当待排序的数组长度较小时，快速排序的递归开销会超过其性能优势，此时可以切换到插入排序，插入排序在小数组上的表现更好。
// 插入排序实现
void insertionSort(vector<int>& arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 优化后的快速排序，小数组用插入排序
void optimizedQuickSort(vector<int>& arr, int low, int high) {
// 数组长度小于10时用插入排序，阈值可以根据实际情况调整
if (high - low + 1 <= 10) {
insertionSort(arr, low, high);
return;
}
int pi = optimizedPartition(arr, low, high);
optimizedQuickSort(arr, low, pi - 1);
optimizedQuickSort(arr, pi + 1, high);
}
3. 尾递归优化
快速排序的递归调用中，先处理较短的部分，再处理较长的部分，可以减少递归栈的深度，避免栈溢出问题。
// 尾递归优化的快速排序
void tailRecursiveQuickSort(vector<int>& arr, int low, int high) {
while (low < high) {
int pi = optimizedPartition(arr, low, high);
// 先处理较短的部分，较长的部分用循环处理
if (pi - low < high - pi) {
tailRecursiveQuickSort(arr, low, pi - 1);
low = pi + 1;
} else {
tailRecursiveQuickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
快速排序的性能分析
优化后的快速排序平均时间复杂度为O(n log n)，最坏情况下如果基准选取合理，也可以接近O(n log n)，空间复杂度主要是递归栈的开销，优化后递归深度可以控制在O(log n)级别。快速排序是不稳定的排序算法，相同元素的相对位置可能会改变，适合对稳定性没有要求的场景使用。