用c++请编程序:对读取的n个正整数采用快速排序法进行排序(升序),统计总共进行了多少次分组,以及中位数是多少(即排序后下标为n/2的元素,如果n是奇数则取整。
时间: 2024-10-13 21:02:22 浏览: 35
在C++中,我们可以编写一个简单的程序,利用快速排序算法对输入的正整数列表进行排序,并同时计算分组次数和中位数。由于快速排序不是稳定的排序算法,所以我们需要手动跟踪分组次数。以下是示例代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
// 快速排序函数
void quickSort(std::vector<int>& arr, int left, int right, int& groupCount) {
if (left >= right)
return;
int pivotIndex = partition(arr, left, right);
groupCount++; // 每次划分算作一次分组
quickSort(arr, left, pivotIndex - 1, groupCount); // 左半部分
quickSort(arr, pivotIndex + 1, right, groupCount); // 右半部分
}
// 划分函数,返回枢轴索引
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;
}
// 计算并打印中位数
double findMedian(std::vector<int>& arr) {
int n = arr.size();
if (n % 2 == 0) { // 如果偶数个元素,取中间两个数的平均值
int mid = n / 2;
return static_cast<double>(arr[mid - 1] + arr[mid]) / 2.0;
} else {
// 如果奇数个元素,直接返回中间的那个数
int mid = n / 2;
return static_cast<double>(arr[mid]);
}
}
int main() {
int n;
std::cout << "Enter the number of integers: ";
std::cin >> n;
std::vector<int> numbers(n);
std::cout << "Enter " << n << " positive integers: ";
for (int& num : numbers) {
std::cin >> num;
}
int groupCount = 0;
quickSort(numbers, 0, numbers.size() - 1, groupCount);
std::cout << "Sorted array: ";
for (const auto& num : numbers) {
std::cout << num << " ";
}
std::cout << "\nTotal groups: " << groupCount << std::endl;
double median = findMedian(numbers);
std::cout << "Median: " << median << std::endl;
return 0;
}
```
在这个程序中,我们首先读入n个整数,然后使用`quickSort`函数进行排序,同时更新`groupCount`。最后,通过`findMedian`函数计算中位数并打印结果。
阅读全文