题目1:给定n个数值,从小到大排序。 要求: 1. 输入随机生成0≦x≦十的九次方数组,长度分别为5、10、100; 2. 采用快速排序输出每次执行的排序结果 3. 时间复杂度、空间复杂度、实际执行时间、实际占用内存空间?给出c++代码
时间: 2024-10-08 12:21:41 浏览: 25
题目1描述的是使用快速排序算法对一组整数进行排序的问题。快速排序是一种高效的排序算法,其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分继续进行排序,直到整个序列有序。
下面是使用C++实现快速排序的一个示例,这里仅考虑了平均情况下的时间复杂度和空间复杂度,因为快速排序在最坏的情况下(输入已经是逆序),时间复杂度会退化到O(n^2),但这种情况并不常见:
```cpp
#include <vector>
#include <cstdlib> // 需要stdlib.h头文件用于rand()
// 快速排序函数
template<typename T>
void quickSort(std::vector<T>& arr, int low, int high) {
if (low < high) {
// 选择基准值并分区
int pivotIndex = partition(arr, low, high);
// 对左右两个子区间递归地进行快速排序
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// 分区函数
template<typename T>
int partition(std::vector<T>& arr, int low, int high) {
T pivotValue = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivotValue) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
// 主函数示例
int main() {
int n;
std::cout << "Enter the number of elements (5, 10 or 100): ";
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; ++i) {
nums[i] = rand() % pow(10, 9); // 随机生成0到10^9之间的整数
}
std::cout << "Before sorting: \n";
for (auto num : nums) {
std::cout << num << " ";
}
std::cout << "\n";
quickSort(nums, 0, n - 1);
std::cout << "After sorting: \n";
for (auto num : nums) {
std::cout << num << " ";
}
// 这里无法直接获取时间复杂度和空间复杂度,需要借助性能分析工具或测试代码运行多次计算
// 时间复杂度:平均 O(n log n), 最坏 O(n^2)
// 空间复杂度:O(log n) (递归栈深度)
return 0;
}
```
阅读全文