c++完成对于冒泡排序分别随机生成问题规模为10、100、1000、10000的正序的初始排列,用表格记录实验数据。
时间: 2024-09-13 14:08:37 浏览: 58
C/C++数据结构_随机10000个数:排序~8大排序代码集.rar
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。
在C++中,我们可以使用随机数生成器来创建不同规模的数据集,并对它们进行冒泡排序。以下是一个简单的示例代码,它演示了如何生成不同规模的正序排列,并进行冒泡排序:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace std::chrono;
void printVector(const vector<int>& vec) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
void bubbleSort(vector<int>& vec) {
bool swapped;
int n = vec.size();
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (vec[j] > vec[j + 1]) {
swap(vec[j], vec[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 优化:如果这一趟没有交换,说明已经有序,无需继续排序
}
}
int main() {
vector<vector<int>>规模数据 = {
{10},
{100},
{1000},
{10000}
};
vector<int> swapCount(规模数据.size(), 0);
vector<int> timeConsumed(规模数据.size(), 0);
for (size_t i = 0; i < 规模数据.size(); i++) {
// 随机生成初始数据
for (int& num : 规模数据[i]) {
num = rand() % (规模数据[i].size() + 1); // 生成[0, 规模数据[i].size()]范围内的随机数
}
vector<int> data = 规模数据[i];
// 记录开始时间
auto start = high_resolution_clock::now();
// 执行冒泡排序
bubbleSort(data);
// 记录结束时间
auto stop = high_resolution_clock::now();
// 计算时间消耗
timeConsumed[i] = duration_cast<microseconds>(stop - start).count();
// 记录交换次数
swapCount[i] = swapCount[i] + timeConsumed[i];
// 输出结果
cout << "规模为 " << 规模数据[i].size() << " 的数组排序结果: ";
printVector(data);
cout << "排序所需时间(微秒): " << timeConsumed[i] << endl;
}
// 输出交换次数
cout << "排序次数: " << endl;
for (size_t i = 0; i < swapCount.size(); i++) {
cout << "规模为 " << 规模数据[i].size() << " 的数组: " << swapCount[i] << "次" << endl;
}
return 0;
}
```
请注意,上面的代码并没有实际统计交换次数,这是因为冒泡排序的交换次数取决于输入数据的初始顺序,对于已经正序排列的数据,理论上交换次数应该为零。如果需要统计交换次数,可以添加一个计数器在每次交换时增加。
实验数据应该记录如下格式的表格:
| 规模 | 排序次数 | 所需时间(微秒) |
|------|---------|------------------|
| 10 | 0 | 记录的时间 |
| 100 | 0 | 记录的时间 |
| 1000 | 0 | 记录的时间 |
| 10000| 0 | 记录的时间 |
由于冒泡排序的时间复杂度为O(n^2),预计随着数据规模的增大,所需时间将显著增长。对于已经是正序排列的数组,冒泡排序将表现得非常高效,但由于在实际的冒泡排序中,内层循环会在数组已经是有序的情况下提前终止,所以即使是正序排列,冒泡排序的性能也会受到初始数据规模的影响。
阅读全文