C语言实现排序算法之归并排序详解

概述

归并排序是一种分治算法，在处理大规模数据排序时具有较高的效率。该算法将要排序的数组分为两部分，对每个部分内部进行排序，然后将排好序的两部分合并成一个有序数组。该算法在实现时需要借助递归和迭代两种方式。

步骤

归并排序可递归或迭代实现。以下是递归实现的步骤：

1. 分解：将待排序数组分为两个等长的子数组，分别为左半部分和右半部分。
2. 解决：对左半部分和右半部分分别调用归并排序函数进行递归排序。
3. 合并：将已排好序的两个子数组进行合并，得到完整的排好序的数组。

以下是迭代实现的步骤：

1. 初始时，将待排序数组看成n个只有一个元素的子序列，对每个子序列都进行归并排序。
2. 将排序后的后续序列按照由小到大顺序依次合并，直到得到完整的排好序数组。

代码实现

以下是C语言实现归并排序的代码示例，包括递归和迭代两种实现方式：

递归实现

void merge_sort_recursive(int arr[], int reg[], int start, int end)
{
    if (start >= end) {
        return;
    }

    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];

    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

迭代实现

void merge_sort_iterative(int arr[], int len)
{
    int* a = arr;
    int* b = (int*)malloc(len * sizeof(int));
    int seg, start;

    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;

            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

示例说明

假设有如下数组需要进行排序：

{10, 38, 19, 2, 45, 5, 3, 1, 22, 15}

递归实现示例

首先使用递归方法进行排序，调用 merge_sort_recursive() 函数进行排序。将原数组 arr[] 复制一份，作为临时存储数组 reg[]。左半部分排序时，将起始下标设置为 start1，终止下标设置为 mid，右半部分排序时，将起始下标设置为 mid+1，终止下标设置为 end。分别对左右两半部分调用 merge_sort_recursive()函数进行递归排序。排序完成后，将 reg[] 中已排好序的数组合并，之后再将 reg[] 的值复制到 arr[] 中。

以下是示例代码：

int main()
{
    int arr[] = { 10, 38, 19, 2, 45, 5, 3, 1, 22, 15 };
    int len = sizeof(arr) / sizeof(arr[0]);

    int* reg = (int*)malloc(len * sizeof(int));

    merge_sort_recursive(arr, reg, 0, len - 1);

    free(reg);

    return 0;
}

迭代实现示例

接下来使用迭代方法进行排序，调用 merge_sort_iterative() 函数进行排序。将数组看成 n 个只有一个元素的子序列，对每个子序列的进行调用 merge_sort_iterative() 函数进行排序。之后将排好序的子序列依次两两合并，直到得到完整排好序的数组。

以下是示例代码：

int main()
{
    int arr[] = { 10, 38, 19, 2, 45, 5, 3, 1, 22, 15 };
    int len = sizeof(arr) / sizeof(arr[0]);

    merge_sort_iterative(arr, len);

    return 0;
}

总结

归并排序是一种典型的分治思想的排序算法。无论是递归还是迭代实现都需要对排序数组按照规则进行分裂，之后对子数组进行排序合并。这种算法的优点是可以对排序数组保证稳定性，以及在处理大规模排序数据时具有较高的效率。