题目1:给定n个数值,从小到大排序。 1.输入随机生成0≦x≦10^9数组,长度分别为5、10、100; 2.采用快速排序输出每次执行的排序结果 3.时间复杂度、空间复杂度、实际执行时间、实际占用内存空间?写出c++的代码
时间: 2024-10-16 21:09:03 浏览: 6
题目1:对于给定一组数值,我们需要对其进行从小到大的排序。我们可以选择快速排序算法,因为它的平均时间复杂度为O(n log n),是一种高效的排序方法。
以下是C++代码实现快速排序对长度分别为5、10、100的随机数组进行排序:
```cpp
#include <iostream>
#include <vector>
#include <cstdlib> // for rand()
#include <ctime> // for srand()
// 用于交换两个元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 快速排序函数
template<int N>
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 pivotValue = arr[high]; // 选择最后一个元素作为基准值
int i = (low - 1); // 小于基准值的元素的下标
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivotValue) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // 将基准值放在正确的位置
return i + 1;
}
int main() {
// 设置随机数种子,保证每次运行得到相同的随机数
std::srand(std::time(0));
// 生成并打印长度为5的随机数组示例
std::vector<int> smallArray(5);
for (int& num : smallArray)
num = rand() % (1 << 30);
std::cout << "Length 5: ";
for (const auto& num : smallArray)
std::cout << num << " ";
std::cout << "\nSorted: ";
quickSort(smallArray, 0, smallArray.size() - 1);
std::cout << "\n";
// 类似地,可以生成长度为10和100的随机数组并进行排序
// ...
return 0;
}
```
**时间复杂度**:平均时间复杂度为O(n log n),最坏情况(数组已排序或逆序)下为O(n^2),但这种情况较少见。
**空间复杂度**:由于快速排序是原地排序算法,其空间复杂度为O(log n),取决于递归栈的深度。
**实际执行时间和实际占用内存空间**:这会依赖于具体的计算机性能以及输入数据的特性,上述代码给出了理论上的分析,但在实际运行中需要通过实验测量。
阅读全文