基于分治法的快速排序的c++代码
时间: 2023-07-25 10:30:10 浏览: 45
好的,以下是基于分治法的快速排序的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[l];
int i = l + 1;
int j = r;
while (true) {
while (i <= j && nums[i] <= pivot) {
i++;
}
while (i <= j && nums[j] >= pivot) {
j--;
}
if (i <= j) {
swap(nums[i], nums[j]);
} else {
break;
}
}
swap(nums[l], nums[j]);
return j;
}
void quickSort(vector<int>& nums, int l, int r) {
if (l < r) {
int pivot = partition(nums, l, r);
quickSort(nums, l, pivot - 1);
quickSort(nums, pivot + 1, r);
}
}
int main() {
vector<int> nums = {3, 5, 1, 4, 2};
quickSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
return 0;
}
```
这段代码中,我们首先定义了 partition 函数,然后定义了 quickSort 函数,其中 quickSort 函数是递归实现快速排序的主体部分。在 main 函数中,我们定义了一个整数向量 nums 并将其初始化为 {3, 5, 1, 4, 2},然后调用 quickSort 函数对其进行排序,并输出排序后的结果。