快速排序c++

快速排序的算法优化

代码如下：

正常的写法：

#include <iostream>
#include <algorithm>// 使用最左边的元素作为 pivot 的分区函数
int partition(int arr[], int left, int right) {int pivot = arr[left];  // 选择最左边的元素作为 pivotint i = left + 1;       // i 从 pivot 后开始int j = right;          // j 从数组最右边开始while (true) {// 找到大于等于 pivot 的元素while (i <= right && arr[i] <= pivot) {i++;}// 找到小于等于 pivot 的元素while (j >= left && arr[j] > pivot) {j--;}if (i >= j) break;  // 如果 i 和 j 交错，结束循环std::swap(arr[i], arr[j]);  // 交换 arr[i] 和 arr[j]}// 将 pivot 放到正确的位置std::swap(arr[left], arr[j]);return j;  // 返回 pivot 的最终位置
}// 快速排序主函数
void quickSort(int arr[], int left, int right) {if (left < right) {// 使用 partition 函数将数组分区int pivotIndex = partition(arr, left, right);// 对左右两部分分别递归进行排序quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}
}// 主函数测试快速排序
int main() {// 测试数组int arr[] = {10, 7, 8, 9, 1, 5, 12, 11, 6, 4, 3, 2};int n = sizeof(arr) / sizeof(arr[0]);// 执行快速排序quickSort(arr, 0, n - 1);// 输出排序后的数组std::cout << "排序后的数组: ";for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}

优化算法

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>// 插入排序，用于处理小数组
void insertionSort(int arr[], int left, int right) {for (int i = left + 1; i <= right; ++i) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];--j;}arr[j + 1] = key;}
}// 三数取中法，优化 pivot 的选择，防止退化为最坏情况
int medianOfThree(int arr[], int left, int right) {int mid = left + (right - left) / 2;if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]);if (arr[left] > arr[right]) std::swap(arr[left], arr[right]);if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]);return arr[mid];  // 取中间值作为 pivot
}// 双向扫描法（Hoare Partition）实现的分区
int hoarePartition(int arr[], int left, int right) {int pivot = medianOfThree(arr, left, right);  // 使用三数取中法选择 pivotint i = left - 1;int j = right + 1;while (true) {do {i++;} while (arr[i] < pivot);do {j--;} while (arr[j] > pivot);if (i >= j) return j;std::swap(arr[i], arr[j]);}
}// 随机化 pivot 选择，减少极端情况下的性能退化
int randomPartition(int arr[], int left, int right) {int randomIndex = left + rand() % (right - left + 1);std::swap(arr[randomIndex], arr[right]);  // 随机选一个 pivot 放到末尾return hoarePartition(arr, left, right);  // 使用 Hoare 分区法
}// 快速排序主函数，结合了插入排序、小数组处理和尾递归优化
void quickSort(int arr[], int left, int right) {const int threshold = 10;  // 阈值，设定小数组使用插入排序while (left < right) {if (right - left <= threshold) {// 小数组使用插入排序insertionSort(arr, left, right);break;}// 使用 Hoare 分区法进行分区int pivotIndex = hoarePartition(arr, left, right);// 选择较小的部分递归处理，减少递归深度，优化尾递归if (pivotIndex - left < right - pivotIndex) {quickSort(arr, left, pivotIndex);  // 递归处理左部分left = pivotIndex + 1;             // 改为处理右部分，减少递归} else {quickSort(arr, pivotIndex + 1, right);  // 递归处理右部分right = pivotIndex;                    // 改为处理左部分，减少递归}}
}// 主函数测试快速排序
int main() {// 测试数组int arr[] = {10, 7, 8, 9, 1, 5, 12, 11, 6, 4, 3, 2};int n = sizeof(arr) / sizeof(arr[0]);// 初始化随机数种子srand(time(0));// 执行快速排序quickSort(arr, 0, n - 1);// 输出排序后的数组std::cout << "排序后的数组: ";for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}