跳到主要内容

归并排序

代码​

C语言代码：

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int* L = (int*) malloc(n1 * sizeof(int));
    int* R = (int*) malloc(n2 * sizeof(int));

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

void merge_sort(int arr[], int n) {
    int curr_size;
    int left_start;

    for (curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size) {
        for (left_start = 0; left_start < n-1; left_start += 2*curr_size) {
            int mid = left_start + curr_size - 1;
            int right_end = (left_start + 2*curr_size - 1 < n-1) ? left_start + 2*curr_size - 1 : n-1;

            merge(arr, left_start, mid, right_end);
        }
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    merge_sort(arr, arr_size);

    printf("\nSorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代码解释​

  1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
  2. 归并函数：
    • merge 函数合并两个有序数组部分，形成一个有序数组。
    • 创建两个临时数组 L 和 R 分别保存左右子数组。
    • 逐个比较临时数组中的元素，将较小的元素放回原数组。
    • 将剩余元素放回原数组。
  3. 归并排序函数：
    • merge_sort 使用自底向上的迭代方法，将数组分割成子数组并合并。
    • 外部循环 curr_size 从1开始，每次翻倍，直到 n-1。
    • 内部循环 left_start 每次移动 2*curr_size 个位置。
    • 计算每一轮合并的中间点和结束点，然后调用 merge 函数进行合并。

示例运行​

假设输入数组为 {12, 11, 13, 5, 6, 7}：

  1. 初始状态：{12, 11, 13, 5, 6, 7}
  2. 第一次合并（curr_size=1）：
    • 合并 {12, 11} 得到 {11, 12}
    • 合并 {13, 5} 得到 {5, 13}
    • 合并 {6, 7} 得到 {6, 7}
    • 状态：{11, 12, 5, 13, 6, 7}
  3. 第二次合并（curr_size=2）：
    • 合并 {11, 12} 和 {5, 13} 得到 {5, 11, 12, 13}
    • 合并 {6, 7} 不变
    • 状态：{5, 11, 12, 13, 6, 7}
  4. 第三次合并（curr_size=4）：
    • 合并 {5, 11, 12, 13} 和 {6, 7} 得到 {5, 6, 7, 11, 12, 13}
    • 最终状态：{5, 6, 7, 11, 12, 13}

时间复杂度分析​

归并排序的时间复杂度主要取决于分割和合并的过程。

  • 最优时间复杂度：O(nlog⁡n)O(n \log n)，因为每次分割数组会递归地分成两半，而每次合并操作需要线性时间。
  • 最坏时间复杂度：O(nlog⁡n)O(n \log n)，无论输入数组的初始顺序如何，执行的步骤基本一致。
  • 平均时间复杂度：O(nlog⁡n)O(n \log n)，对于大多数输入数组，归并排序的性能都很稳定。

空间复杂度分析​

归并排序需要额外的辅助空间来存储临时子数组，因此空间复杂度为 O(n)O(n)。

优缺点​

优点：

  • 时间复杂度稳定，适用于大规模数据排序。
  • 稳定排序算法，不改变相同元素的相对顺序。
  • 分治策略容易并行化实现。

缺点：

  • 需要额外的辅助空间，空间复杂度较高。
  • 实现复杂度相对较高，理解和编程上比简单排序算法复杂。

适用场景​

归并排序适用于以下场景：

  • 数据量较大的排序。
  • 需要一个稳定且高效的排序算法时。
  • 在并行计算环境中使用，归并排序能很好地利用多处理器。

总结​

归并排序是一种高效的排序算法，通过分治策略将数组分成较小的子数组，分别排序后再合并。尽管其实现复杂度较高且需要额外空间，但在处理大规模数据时表现优异，是一种稳定且性能良好的排序算法。