本文共 2672 字，大约阅读时间需要 8 分钟。

优化后的内容

1. 基于递归的归并排序实现

1.1 打印函数

该函数用于在控制台打印数组内容，便于测试和调试。具体实现如下：

void Print(int* array, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

1.2 排序函数

该函数将数组拆分为两部分，然后进行排序。具体实现如下：

void MergeData(int* array, int left, int mid, int right, int* temp) {
    int begin1 = left, end1 = mid;
    int begin2 = mid, end2 = right;
    int index = left;
    while (begin1 < end1 && begin2 < end2) {
        if (array[begin1] <= array[begin2]) {
            temp[index++] = array[begin1++];
        } else {
            temp[index++] = array[begin2++];
        }
    }
    while (begin1 < end1) {
        temp[index++] = array[begin1++];
    }
    while (begin2 < end2) {
        temp[index++] = array[begin2++];
    }
}

1.3 递归排序函数

该函数采用递归的方式实现归并排序。具体实现如下：

void _MergeSort(int* array, int left, int right, int* temp) {
    if (right - left > 1) {
        int mid = left + ((right - left) >> 1);
        _MergeSort(array, left, mid, temp);
        _MergeSort(array, mid, right, temp);
        MergeData(array, left, mid, right, temp);
        memcpy(array + left, temp + left, (right - left) * sizeof(array[0]));
    }
}

1.4 调用函数

该函数负责初始化辅助数组并调用递归函数。具体实现如下：

void MergeSort(int* array, int size) {
    int* temp = (int*)malloc(sizeof(array[0]) * size);
    if (temp == NULL) {
        assert(0);
        return;
    }
    _MergeSort(array, 0, size, temp);
    free(temp);
}

2. 基于循环的归并排序优化

2.1 简单描述

这种方法借助“gap”变量将排序范围不断扩大，每次处理更多元素。具体实现如下：

2.2 代码实现

void MergeSortNor(int* array, int size) {
    int gap = 1; // 初始化间隔
    int* temp = (int*)malloc(sizeof(array[0]) * size);
    if (temp == NULL) {
        assert(0);
        return;
    }
    // 依次扩大gap范围
    while (gap < size) {
        // 循环处理当前范围内的元素
        for (int i = 0; i < size; i += 2 * gap) {
            int left = i;
            int mid = left + gap;
            int right = mid + gap;
            // 防止越界
            if (mid > size) mid = size;
            if (right > size) right = size;
            MergeData(array, left, mid, right, temp);
        }
        // 拷贝排序结果回到原数组
        memcpy(array, temp, size * sizeof(array[0]));
        // 更新gap
        gap <<= 1; // 当前gap乘以2，逐步扩大范围
    }
    free(temp);
}

3. 测试代码

int main() {
    int array[] = {8, 2, 1, 5, 3, 4, 7, 6, 9, 0};
    Print(array, sizeof(array) / sizeof(array[0]));
    // 仅为示例，用户应根据实际需求调用并解释
    // MergeSortNor(array, sizeof(array) / sizeof(array[0]));
    Print(array, sizeof(array) / sizeof(array[0]));
}

4. 功能说明

4.1 递归实现

该方法通过递归将数组不断分成两部分进行排序，最终归并后返回，从而实现归并排序。

4.2 循环优化

通过逐步增加间隔值（gap），该方法简化了递归的复杂性，逐步扩大排序范围，提升效率。

4.3 测试示例

提供了一个排序前后的测试示例，可用于验证排序功能的正确性。

以上代码可根据项目需求选择使用递归或循环实现。递归实现更直观，循环实现可能在内存使用或性能上更为优化。