用c语言实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成, 运行程序,分别记录对十万,一百万,五千万,一千万个数据排序所用的时间, 列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。*/
时间: 2024-10-08 13:17:39 浏览: 90
在C语言中实现合并排序算法,首先需要创建一个辅助函数`merge`用于合并两个已排序的部分,然后主函数`merge_sort`会递归地将数组划分为两半直至每个部分只有一个元素,最后通过`merge`将它们合并成有序序列。
以下是合并排序的基本步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 辅助函数,合并两个已经排序的数组
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
int i = 0, j = 0, k = 0;
while (i < left_size && j < right_size) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left_size) {
arr[k++] = left[i++];
}
while (j < right_size) {
arr[k++] = right[j++];
}
}
// 合并排序函数
void merge_sort(int arr[], int size) {
if (size < 2) return; // 如果数组大小为1或0,视为已排序
int mid = size / 2;
int* left = malloc(mid * sizeof(int)); // 左半部分
int* right = malloc((size - mid) * sizeof(int)); // 右半部分
// 分割并复制数据到左右数组
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
// 对左右数组递归排序,然后合并
merge_sort(left, mid);
merge_sort(right, size - mid);
merge(arr, left, mid, right, size - mid);
free(left);
free(right);
}
// 测试排序
int main() {
srand(time(0));
const int test_sizes[] = {100000, 1000000, 5000000, 10000000};
int data[100]; // 使用100个数据示例
for (int i = 0; i < 100; i++) {
data[i] = rand() % 1000; // 生成0-999之间的随机数
}
printf("Sorting small array of 100 elements:\n");
clock_t start = clock();
merge_sort(data, 100);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken: %.6f seconds\n", time_taken);
// 记录大数组排序时间
for (int i = 0; i < sizeof(test_sizes) / sizeof(test_sizes[0]); i++) {
int* big_data = malloc(test_sizes[i] * sizeof(int));
for (int j = 0; j < test_sizes[i]; j++) {
big_data[j] = rand() % 1000;
}
start = clock();
merge_sort(big_data, test_sizes[i]);
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Sorting array of %d elements: Time taken: %.6f seconds\n", test_sizes[i], time_taken);
free(big_data);
}
return 0;
}
```
当你运行这个程序,它将会输出100个随机数的排序时间和不同规模数组排序所需的时间。注意,实际运行中请确保有足够的内存分配给大数组,并且这个程序可能需要一些时间才能完成对于大数组的排序。
阅读全文