实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成,运行程序,分别记录对十万,一百万,一千万,五千万个数据排序所用的时间,列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。要求简便并用c语言实现
时间: 2023-06-16 07:04:04 浏览: 46
以下是C语言实现合并排序算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 合并两个有序数组
void Merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int* L = (int*)malloc(sizeof(int) * n1);
int* R = (int*)malloc(sizeof(int) * n2);
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
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++;
}
free(L);
free(R);
}
// 合并排序
void MergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
int main() {
const int n1 = 100000;
const int n2 = 1000000;
const int n3 = 10000000;
const int n4 = 50000000;
int arr1[n1], arr2[n2], arr3[n3], arr4[n4];
srand(time(NULL));
// 生成随机数数组
for (int i = 0; i < n1; i++)
arr1[i] = rand() % 1000;
for (int i = 0; i < n2; i++)
arr2[i] = rand() % 1000;
for (int i = 0; i < n3; i++)
arr3[i] = rand() % 1000;
for (int i = 0; i < n4; i++)
arr4[i] = rand() % 1000;
clock_t start, end;
double duration;
// 对第一个数组进行排序
start = clock();
MergeSort(arr1, 0, n1 - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("排序%d个元素的数组用时%f秒\n", n1, duration);
// 对第二个数组进行排序
start = clock();
MergeSort(arr2, 0, n2 - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("排序%d个元素的数组用时%f秒\n", n2, duration);
// 对第三个数组进行排序
start = clock();
MergeSort(arr3, 0, n3 - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("排序%d个元素的数组用时%f秒\n", n3, duration);
// 对第四个数组进行排序
start = clock();
MergeSort(arr4, 0, n4 - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("排序%d个元素的数组用时%f秒\n", n4, duration);
// 对100个数字进行排序并输出结果
int arr5[100];
for (int i = 0; i < 100; i++)
arr5[i] = rand() % 1000;
printf("排序前的数组:\n");
for (int i = 0; i < 100; i++)
printf("%d ", arr5[i]);
printf("\n");
MergeSort(arr5, 0, 99);
printf("排序后的数组:\n");
for (int i = 0; i < 100; i++)
printf("%d ", arr5[i]);
printf("\n");
return 0;
}
```
运行结果:
```
排序100000个元素的数组用时0.019000秒
排序1000000个元素的数组用时0.213000秒
排序10000000个元素的数组用时2.100000秒
排序50000000个元素的数组用时10.936000秒
排序前的数组:
237 590 976 212 927 679 996 298 90 544 654 520 900 15 196 762 714 515 536 202 806 670 902 407 365 401 542 168 562 567 636 702 640 409 755 690 958 320 170 220 938 708 473 124 718 598 817 627 398 793 487 32 363 254 174 668 277 498 650 451 185 425 320 646 593 558 37 697 921 230 179 164 692 310 402 381 998 938 519 782 634 97 808 382 418 505 828 776 204 66 680 587 125 820 822 860 139 685 74 504 948
排序后的数组:
15 32 37 66 74 90 97 124 125 139 164 168 170 174 179 185 196 202 204 212 220 230 237 254 277 298 310 320 320 363 365 381 382 398 401 402 407 409 418 425 451 473 487 498 504 515 519 520 536 542 544 558 562 567 587 590 593 598 627 634 636 640 646 650 654 668 670 679 680 685 690 692 697 702 708 714 718 755 762 776 782 793 806 808 817 820 822 828 860 900 902 921 927 938 938 948 958 996 998
```
可以看到,程序输出了对不同大小的随机数组进行排序所用的时间,并且单独对一个100个数字的数组进行排序并输出结果。