用c++实现上述问题
时间: 2024-09-13 12:02:42 浏览: 23
在C++中实现快速排序算法,你可以按照以下步骤进行:
```cpp
#include <vector>
#include <cstdlib>
// 选择随机索引作为基准
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[low]; // 假设low是基准位置
while (low < high) {
while (low < high && arr[high] >= pivot) { // 从右向左找到第一个小于基准的元素
high--;
}
arr[low] = arr[high]; // 把它放到基准左边
while (low < high && arr[low] < pivot) { // 从左向右找到第一个大于等于基准的元素
low++;
}
arr[high] = arr[low]; // 把它放到基准右边
}
arr[low] = pivot; // 最终把基准放回原位
return low;
}
// 快速排序主函数
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区并得到基准的位置
quickSort(arr, low, pi - 1); // 对基准左边的部分递归排序
quickSort(arr, pi + 1, high); // 对基准右边的部分递归排序
}
}
int main() {
std::vector<int> test_array = {5, 3, 6, 2, 8, 1};
quickSort(test_array, 0, test_array.size() - 1);
std::cout << "Sorted array: ";
for (const auto& num : test_array) {
std::cout << num << " ";
}
std::cout << "\n";
return 0;
}
```
这个C++版本的快速排序实现了选择第一个元素作为基准,并使用两个指针从两端开始寻找应该交换的值。注意,实际应用中可能会选择更复杂的随机基准选取方法来提高效率。