随机快速排序cpp代码
时间: 2024-09-20 16:12:37 浏览: 32
随机快速排序是一种改进版的快速排序算法,它通过随机选择基准元素来避免最坏情况的发生,即每次选择的基准都是最大值或最小值导致划分不均衡的情况。下面是简单的C++代码实现:
```cpp
#include <iostream>
#include <cstdlib> // 包含随机数生成库
#include <ctime>
// 定义快速排序函数
template<typename T>
void quicksort(T arr[], int low, int high) {
if (low < high) {
// 选取随机的基准点
srand(time(0)); // 设置随机种子
int pivotIndex = low + rand() % (high - low + 1);
std::swap(arr[low], arr[pivotIndex]);
// 分区过程
int i = low, j = high;
while (i <= j) {
while (arr[i] < arr[low]) i++;
while (arr[j] > arr[low]) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++;
j--;
}
}
// 递归对左右两边进行排序
quicksort(arr, low, j);
quicksort(arr, i, high);
}
}
int main() {
int nums[] = {9, 7, 5, 11, 12, 2, 14, 3};
int size = sizeof(nums) / sizeof(nums[0]);
std::cout << "Before sorting:\n";
for (int num : nums)
std::cout << num << " ";
std::cout << "\n";
quicksort(nums, 0, size - 1);
std::cout << "After sorting:\n";
for (int num : nums)
std::cout << num << " ";
std::cout << "\n";
return 0;
}
```
这个代码首先定义了一个模板`quicksort`,用于对任意类型的数组进行排序。在主函数里,我们创建了一个整数数组并调用了`quicksort`对其进行排序。
阅读全文