一、归并排序算法
基本思想
归并排序采用分治法策略，将数组递归地分成两半，然后对每一半进行排序，最后将两个已排序的子数组合并成一个完整的有序数组。
步骤
- 递归划分：将数组分成两半，直到每个子数组只有一个元素。
- 递归排序：递归地对每个子数组进行排序。
- 合并子数组：将排序后的子数组合并成一个有序数组。
示例
假设我们有一个数组 [5, 2, 4, 6, 1, 3]：
- 划分：
[5, 2, 4, 6, 1, 3]->[5, 2, 4]和[6, 1, 3] - 递归划分：
[5, 2, 4]->[5]和[2, 4][6, 1, 3]->[6]和[1, 3]
- 递归排序：
[2, 4]->[2]和[4]->[2, 4][1, 3]->[1]和[3]->[1, 3]
- 合并子数组：
[5]和[2, 4]->[2, 4, 5][6]和[1, 3]->[1, 3, 6]
- 最终合并：
[2, 4, 5]和[1, 3, 6]->[1, 2, 3, 4, 5, 6]
性能分析
- 时间复杂度：O(n log n)（无论最好、平均还是最坏情况）
- 空间复杂度：O(n)（需要额外的存储空间用于临时数组）
二、代码
#include <stdlib.h>
#include <stdio.h>
#include <time.h>// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void merge_sort(int *array, int *temp, int left, int right);
void merge(int *array, int *temp, int left, int mid, int right);
int generate_random_size();int main() {int size = generate_random_size(); // 随机生成数组大小int *array = create_and_generate_random_array(size);int *temp = (int *)malloc(sizeof(int) * size); // 临时数组用于归并排序if (array == NULL || temp == NULL) {// 如果内存分配失败printf("Memory allocation failed\n");free(array);free(temp);return 1;}// 打印原始数组（如果需要，可以取消注释）// printf("Original array:\n");// print_array(array, size);// 获取开始时间clock_t start_time = clock();// 对数组进行归并排序merge_sort(array, temp, 0, size - 1);// 获取结束时间clock_t end_time = clock();// 计算时间差并转换为毫秒double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;// 打印排序后的数组（如果需要，可以取消注释）// printf("Sorted array:\n");// print_array(array, size);printf("array_size = %d\n", size);// 打印执行时间printf("Execution time: %.2f ms\n", execution_time);// 释放分配的内存free(array);free(temp);return 0;
}// 生成随机数组大小
int generate_random_size() {srand(time(NULL));return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}// 创建并生成随机数组
int* create_and_generate_random_array(int size) {int *array = (int *)malloc(sizeof(int) * size);if (array == NULL) {// 如果内存分配失败return NULL;}// 使用当前时间作为随机数种子srand(time(NULL));for (int i = 0; i < size; i++) {array[i] = rand() % 1000; // 生成0到999之间的随机数}return array;
}// 打印数组
void print_array(int *array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");
}// 归并排序
void merge_sort(int *array, int *temp, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 递归地排序左右两个子数组merge_sort(array, temp, left, mid);merge_sort(array, temp, mid + 1, right);// 合并两个已排序的子数组merge(array, temp, left, mid, right);}
}// 合并两个已排序的子数组
void merge(int *array, int *temp, int left, int mid, int right) {int i, j, k;// 复制数据到临时数组for (i = left; i <= right; i++) {temp[i] = array[i];}i = left;j = mid + 1;k = left;// 合并两个子数组while (i <= mid && j <= right) {if (temp[i] <= temp[j]) {array[k] = temp[i];i++;} else {array[k] = temp[j];j++;}k++;}// 复制剩余元素while (i <= mid) {array[k] = temp[i];i++;k++;}
}
