快速排序的核心逻辑是通过选取基准值将序列划分为两部分，再递归处理子序列完成排序。传统快速排序如果每次都选取首元素或尾元素作为基准，当待排序序列本身有序时，每次划分只能减少一个元素，时间复杂度会退化到O(n²)。三数取中法通过选取首、中、尾三个元素的中间值作为基准，能有效避免这种最坏情况。
三数取中法的核心逻辑
三数取中法的实现步骤如下：
- 获取待划分区间的首元素索引
left、尾元素索引right、中间元素索引mid = left + (right - left) / 2 - 对比三个位置的元素值，找到大小处于中间的元素
- 将该中间元素与区间首元素交换，后续仍使用首元素作为基准进行划分
完整C++实现源码
三数取中辅助函数
首先实现获取三个数中中间值的函数，负责完成基准值的选取和交换操作：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 三数取中函数，返回基准值的位置，同时将基准值交换到left位置
int medianOfThree(vector<int>& arr, int left, int right) {
int mid = left + (right - left) / 2;
// 先保证arr[left] <= arr[mid]
if (arr[left] > arr[mid]) {
swap(arr[left], arr[mid]);
}
// 再保证arr[mid] <= arr[right]
if (arr[mid] > arr[right]) {
swap(arr[mid], arr[right]);
}
// 最后保证arr[left] <= arr[mid]
if (arr[left] > arr[mid]) {
swap(arr[left], arr[mid]);
}
// 此时arr[mid]是三个数的中间值，将其交换到left位置作为基准
swap(arr[left], arr[mid]);
return left;
}
划分函数实现
划分函数采用双指针法，从区间两端向中间遍历，将小于基准的元素移到左侧，大于基准的元素移到右侧：
int partition(vector<int>& arr, int left, int right) {
// 调用三数取中获取基准值，基准值已经交换到left位置
int pivotIndex = medianOfThree(arr, left, right);
int pivot = arr[pivotIndex];
int i = left + 1;
int j = right;
while (true) {
// 从左向右找第一个大于等于基准的元素
while (i <= j && arr[i] < pivot) {
i++;
}
// 从右向左找第一个小于等于基准的元素
while (i <= j && arr[j] > pivot) {
j--;
}
if (i >= j) {
break;
}
// 交换两个不符合位置的元素
swap(arr[i], arr[j]);
i++;
j--;
}
// 将基准值放到正确的位置
swap(arr[left], arr[j]);
return j;
}
快速排序主函数
递归调用划分函数完成整个序列的排序：
void quickSort(vector<int>& arr, int left, int right) {
if (left >= right) {
return;
}
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos - 1);
quickSort(arr, pivotPos + 1, right);
}
// 对外暴露的排序接口
void quickSort(vector<int>& arr) {
if (arr.empty()) {
return;
}
quickSort(arr, 0, arr.size() - 1);
}
测试代码
编写测试代码验证优化后的快速排序效果：
int main() {
// 测试有序序列，传统快速排序会退化到O(n²)，三数取中法可避免
vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
quickSort(arr1);
cout << "有序序列排序结果：";
for (int num : arr1) {
cout << num << " ";
}
cout << endl;
// 测试随机序列
vector<int> arr2 = {9, 5, 1, 8, 3, 7, 2, 6, 4};
quickSort(arr2);
cout << "随机序列排序结果：";
for (int num : arr2) {
cout << num << " ";
}
cout << endl;
return 0;
}
优化效果分析
传统快速排序的平均时间复杂度是O(n log n)，最坏情况为O(n²)。三数取中法通过优化基准值选取，使得每次划分的区间尽可能均匀，几乎可以避免最坏时间复杂度的出现，在待排序序列本身有序或接近有序的场景下，性能提升非常明显。同时该优化不会增加额外的空间开销，仅多几次元素比较和交换操作，整体效率优于传统实现。