c语言归并排序代码详细注释,C语言实现归并排序算法

以下是C语言实现归并排序算法的代码和注释：

#include <stdio.h>

/* 归并排序函数 */
void merge_sort(int arr[], int left, int right);

/* 合并两个有序数组 */
void merge(int arr[], int left, int mid, int right);

/* 主函数 */
int main() {
    int arr[] = {3, 5, 1, 2, 6, 4};
    int len = sizeof(arr) / sizeof(arr[0]);  // 数组长度
    merge_sort(arr, 0, len - 1);  // 调用归并排序
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);  // 输出排序后的数组
    }
    return 0;
}

void merge_sort(int arr[], int left, int right) {
    if (left >= right) {
        return;  // 当数组只有一个元素时，直接返回
    }
    int mid = (left + right) / 2;  // 求中间位置
    merge_sort(arr, left, mid);  // 对左半部分进行递归排序
    merge_sort(arr, mid + 1, right);  // 对右半部分进行递归排序
    merge(arr, left, mid, right);  // 合并左右两个有序数组
}

void merge(int arr[], int left, int mid, int right) {
    int len = right - left + 1;
    int *tmp = (int*)malloc(len * sizeof(int));  // 申请临时数组
    int i = left;  // 左半部分数组起始位置
    int j = mid + 1;  // 右半部分数组起始位置
    int k = 0;  // 临时数组起始位置
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];  // 将左半部分数组元素放入临时数组中
        } else {
            tmp[k++] = arr[j++];  // 将右半部分数组元素放入临时数组中
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];  // 将剩余的左半部分数组元素放入临时数组中
    }
    while (j <= right) {
        tmp[k++] = arr[j++];  // 将剩余的右半部分数组元素放入临时数组中
    }
    for (int m = 0; m < len; m++) {
        arr[left + m] = tmp[m];  // 将临时数组中的元素复制回原数组中
    }
    free(tmp);  // 释放临时数组的内存空间
}

代码注释：

1. `merge_sort`函数：归并排序函数，用于将数组的左半部分和右半部分进行递归排序，并将两个有序数组合并成一个有序数组。参数`arr`为要排序的数组，参数`left`为数组左边界，参数`right`为数组右边界。

2. `merge`函数：合并两个有序数组，用于将数组的左半部分和右半部分合并成一个有序数组。参数`arr`为原始数组，参数`left`为左半部分数组的起始位置，参数`mid`为左半部分数组的终止位置，参数`right`为右半部分数组的终止位置。

3. `main`函数：主函数，用于测试归并排序的效果。

4. 在`merge`函数中，首先计算出临时数组的长度，然后申请临时数组的内存空间。接着，使用双指针法将左半部分数组和右半部分数组进行合并，将合并后的有序数组存放在临时数组中。最后，将临时数组中的元素复制回原数组中，并释放临时数组的内存空间。

5. 在`merge_sort`函数中，首先判断数组是否只有一个元素，如果是，则直接返回。否则，计算出数组的中间位置`mid`，然后对数组的左半部分和右半部分进行递归排序，并将排序后的两个有序数组合并成一个有序数组。