题目:给定n个数值,从小到大排序。 要求: 1.输入随机生成0≦x≦10^9数组,长度分别为5、10、100; 2.采用快速排序输出每次执行的排序结果 写出c++代码
时间: 2024-10-17 15:05:03 浏览: 2
题目描述是要实现一个快速排序算法对随机生成的整数数组进行排序。以下是使用C++编写的快速排序示例代码:
```cpp
#include <iostream>
#include <vector>
#include <cstdlib> // 引入rand和srand函数
using namespace std;
// 选择第一个元素作为基准
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[low]; // 基准值
while (low < high) {
while (low < high && arr[high] >= pivot) high--;
if (low != high)
arr[low++] = arr[high];
while (low < high && arr[low] <= pivot) low++;
if (low != high)
arr[high--] = arr[low];
}
arr[low] = pivot;
return low;
}
// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // 对左侧部分递归排序
quickSort(arr, pi + 1, high); // 对右侧部分递归排序
}
}
int main() {
srand(time(0)); // 设置随机数种子
// 测试不同长度的数组
for (int n : {5, 10, 100}) {
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = rand() % (1 << 30); // 生成0~10^9范围内的随机数
}
cout << "排序前: ";
for (const auto& num : arr) {
cout << num << " ";
}
cout << endl;
quickSort(arr, 0, arr.size() - 1);
cout << "排序后: ";
for (const auto& num : arr) {
cout << num << " ";
}
cout << endl << endl;
}
return 0;
}
```
阅读全文