题目1:给定n个数值,从小到大排序。 要求: 输入随机生成0≦x≦十的九次方数组,长度分别为5、10、100; 采用快速排序输出每次执行的排序结果 时间复杂度、空间复杂度、实际执行时间、实际占用内存空间?给出c++代码
时间: 2024-10-08 19:23:54 浏览: 29
题目1描述的是对一组整数数组进行排序的任务,这里选择快速排序算法来完成。快速排序是一种高效的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序。
以下是使用C++实现快速排序,并满足题目要求的一个示例:
```cpp
#include <iostream>
#include <vector>
#include <cstdlib> //用于random库生成随机数
#include <ctime> //设置随机数种子
// 快速排序函数
void quickSort(std::vector<int>& nums, int low, int high) {
if (low < high) {
int pivotIndex = partition(nums, low, high);
quickSort(nums, low, pivotIndex - 1); // 对左半部分递归排序
quickSort(nums, pivotIndex + 1, high); // 对右半部分递归排序
}
}
// 分区函数,返回基准元素的索引
int partition(std::vector<int>& nums, int low, int high) {
int pivot = nums[high]; // 通常选取数组尾部作为基准
int i = low - 1;
for (int j = low; j < high; ++j) {
if (nums[j] <= pivot) {
i++;
std::swap(nums[i], nums[j]);
}
}
std::swap(nums[i + 1], nums[high]);
return i + 1;
}
int main() {
// 设置随机数种子,保证每次运行程序得到的结果一致
srand(time(0));
// 示例:生成长度为5、10和100的随机数组
int n;
std::cout << "Enter the length of the array: ";
std::cin >> n;
switch (n) {
case 5:
std::vector<int> smallArray(5);
generateRandomArray(smallArray);
std::cout << "Sorting a 5-element array...\n";
quickSort(smallArray, 0, smallArray.size() - 1);
printArray(smallArray);
break;
case 10:
std::vector<int> mediumArray(10);
generateRandomArray(mediumArray);
std::cout << "Sorting a 10-element array...\n";
quickSort(mediumArray, 0, mediumArray.size() - 1);
printArray(mediumArray);
break;
case 100:
std::vector<int> largeArray(100);
generateRandomArray(largeArray);
std::cout << "Sorting a 100-element array...\n";
quickSort(largeArray, 0, largeArray.size() - 1);
printArray(largeArray);
break;
default:
std::cerr << "Invalid input. Exiting.\n";
return 1;
}
return 0;
}
// 生成指定长度的随机数组
void generateRandomArray(std::vector<int>& arr) {
for (size_t i = 0; i < arr.size(); ++i) {
arr[i] = rand() % 1e9; // 生成0到10^9之间的随机数
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
std::cout << "Sorted array: ";
for (const auto& num : arr) {
std::cout << num << " ";
}
std::cout << "\n";
}
// 时间复杂度:平均情况下的时间复杂度为O(n log n),最坏情况(如已经排序或完全逆序)下为O(n^2)
// 空间复杂度:取决于递归栈的深度,平均O(log n),最坏O(n)(如果所有元素都相同)
```
**相关问题--:**
1. 快速排序的时间复杂度是什么?
2. 这段代码如何处理大规模数据?
3. 实际执行时间和占用内存如何测量?
阅读全文