用c++写分治法快速排序,要求数据量小于40时用冒泡排序,大于40用快速排序
时间: 2024-09-27 17:16:44 浏览: 40
在 C++ 中,你可以通过条件判断结合分治法和冒泡排序的方式来实现快速排序的策略调整。这里是一个简单的示例:
```cpp
#include <iostream>
#include <vector>
// 使用冒泡排序处理小规模数据
void bubbleSort(std::vector<int>& arr, int size) {
if (size <= 40) { // 如果数据量小于等于40,采用冒泡排序
for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
} else { // 否则,使用快速排序
quickSort(arr, 0, size - 1);
}
}
// 快速排序函数
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 分区操作
quickSort(arr, low, pivotIndex - 1); // 对左半部分递归调用
quickSort(arr, pivotIndex + 1, high); // 对右半部分递归调用
}
}
// 分区函数,用于快速排序
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]); // 将基准放到正确的位置
return i + 1;
}
int main() {
std::vector<int> nums = { /* 一些随机数 */ };
bubbleSort(nums, nums.size());
for (const auto& num : nums) {
std::cout << num << " ";
}
std::cout << "\n";
阅读全文