用C++实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成,运行程序,分别记录对十万,一百万,一千万,五千万个数据排序所用的时间,列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。
时间: 2024-03-14 17:44:46 浏览: 55
好的,我可以帮你回答这个问题。下面是用C++实现合并排序算法的代码:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
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);
}
}
int main()
{
srand(time(NULL));
int n[4] = {100000, 1000000, 10000000, 50000000};
for (int i = 0; i < 4; i++)
{
int* arr = new int[n[i]];
for (int j = 0; j < n[i]; j++)
arr[j] = rand() % 1000000;
clock_t start = clock();
mergeSort(arr, 0, n[i] - 1);
clock_t end = clock();
double time = (double)(end - start) / CLOCKS_PER_SEC;
cout << "Sorting " << n[i] << " elements took " << time << " seconds.\n";
delete[] arr;
}
int* arr = new int[100];
cout << "Before sorting: ";
for (int i = 0; i < 100; i++)
{
arr[i] = rand() % 100;
cout << arr[i] << " ";
}
cout << endl;
mergeSort(arr, 0, 99);
cout << "After sorting: ";
for (int i = 0; i < 100; i++)
{
cout << arr[i] << " ";
}
cout << endl;
delete[] arr;
return 0;
}
```
这段代码使用了随机数生成器生成需要排序的整型数组元素,然后分别对10万,100万,1000万和5000万个数据进行排序,并记录排序所用的时间。最后,将100个数据进行排序,并输出排序结果。
你可以将代码保存为`sorting.cpp`文件,然后在命令行中使用以下命令编译和运行程序:
```
g++ -o sorting sorting.cpp
./sorting
```
程序将输出各个数据量排序所用的时间,并输出100个数据的排序结果。
阅读全文