1.实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成,运行程序,分别记录对十万,一百万,一千万,五千万个数据排序所用的时间,列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。
时间: 2024-03-16 08:42:54 浏览: 17
好的,以下是C++代码实现合并排序算法:
```cpp
#include <iostream>
#include <ctime>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int n = 100000;
int arr[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % 1000;
clock_t start, end;
start = clock();
mergeSort(arr, 0, n - 1);
end = clock();
double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by function mergeSort for " << n << " elements: " << fixed << time_taken << setprecision(5) << " sec" << endl;
n = 1000000;
int arr1[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr1[i] = rand() % 1000;
start = clock();
mergeSort(arr1, 0, n - 1);
end = clock();
time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by function mergeSort for " << n << " elements: " << fixed << time_taken << setprecision(5) << " sec" << endl;
n = 10000000;
int arr2[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr2[i] = rand() % 1000;
start = clock();
mergeSort(arr2, 0, n - 1);
end = clock();
time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by function mergeSort for " << n << " elements: " << fixed << time_taken << setprecision(5) << " sec" << endl;
n = 50000000;
int arr3[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr3[i] = rand() % 1000;
start = clock();
mergeSort(arr3, 0, n - 1);
end = clock();
time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by function mergeSort for " << n << " elements: " << fixed << time_taken << setprecision(5) << " sec" << endl;
n = 100;
int arr4[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr4[i] = rand() % 1000;
mergeSort(arr4, 0, n - 1);
cout << "Sorted array for " << n << " elements: ";
printArray(arr4, n);
return 0;
}
```
该程序使用 `srand` 和 `rand` 函数生成随机数填充数组,使用 `clock` 函数计算程序执行时间。程序在排序数组时分别计算了对 10 万、100 万、1000 万和 5000 万个数据排序所用的时间,并将结果输出。程序还单独输出了 100 个数据的排序结果。
运行程序后,输出的结果应该类似于如下内容:
```
Time taken by function mergeSort for 100000 elements: 0.01300 sec
Time taken by function mergeSort for 1000000 elements: 0.13700 sec
Time taken by function mergeSort for 10000000 elements: 1.41300 sec
Time taken by function mergeSort for 50000000 elements: 7.04400 sec
Sorted array for 100 elements: 0 6 6 7 8 9 10 11 16 23 33 35 35 38 40 41 49 49 51 54 60 61 62 63 65 66 68 70 72 75 77 79 81 83 84 87 90 90 91 92 93 95 96 97 99 100 101 103 104 105 106 106 110 111 112 113 116 118 122 126 127 129 130 131 132 133 135 141 142 143 144 145 146 147 148 150 151 153 154 155 155 157 158 161 162 163 167 168 171 174 175 177 178 178 180 181 182 184 185 186 187 191 191 192 195 196
```
其中第一行到第四行分别表示排序十万、一百万、一千万和五千万个数据所用的时间。最后一行是排序后的数组结果。