随机快速排序算法c++
时间: 2023-07-01 16:24:13 浏览: 64
好的,以下是C++实现的随机快速排序算法:
```cpp
#include <iostream>
#include <vector>
#include <random>
using namespace std;
// 随机数生成器
mt19937 rng(random_device{}());
// 将数组分为以pivot为界的两部分,返回pivot的索引
int partition(vector<int>& nums, int left, int right) {
uniform_int_distribution<int> uni(left, right); // 生成[left, right]范围内的随机整数
int pivotIndex = uni(rng); // 随机选择pivot的索引
int pivot = nums[pivotIndex];
swap(nums[pivotIndex], nums[right]); // 将pivot放到最右边
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[right]);
return i;
}
void quickSort(vector<int>& nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
int main() {
vector<int> nums = {5, 3, 2, 8, 6, 7, 1, 4};
quickSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
return 0;
}
```
此处使用了C++11中的随机数生成器mt19937和uniform_int_distribution,可以生成均匀分布的随机数,从而随机选择pivot。