二路归并排序


设计

二路归并排序的原理就是将一个数组分成两个数组,分别对两个数组进行排序,最后将两个数组合为一个数组完成排序。在这个过程中,涉及到了“分治算法”,使用了递归。

代码

#include <stdio.h>

void merge(int a[], int b[], int low, int mid, int high)
{
    int i = low, j = mid + 1, k = low;
    while (i != mid + 1 && j != high + 1)
    {
        if (a[i] > a[j])
            b[k++] = a[j++];
        else
            b[k++] = a[i++];
    }
    while (i != mid + 1)
        b[k++] = a[i++];
    while (j != high + 1)
        b[k++] = a[j++];
    for (i = low; i <= high; i++)
        a[i] = b[i];
}

void merge_sort(int a[], int b[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        merge_sort(a, b, low, mid);
        merge_sort(a, b, mid + 1, high);
        merge(a, b, low, mid, high);
    }
}

int main()
{
    int length;
    printf("请输入要排序元素的个数:");
    scanf("%d", &length);
    //int a[15] = {50, 10, 20, 30, 70, 40, 80, 60, 45, 66, 38, 29, 51,74, 13};
    //int i, b[15];
    int a[length];
    printf("输入要排序的数列:");
    for (int i = 0; i < length; i++)
        scanf("%d", &a[i]);
    int b[length];
    printf("原顺序为: \n");
    for (int j = 0; j < length; j++)
        printf("%d ", a[j]);
    merge_sort(a, b, 0, length - 1);
    printf("\n二路归并排序后的顺序为: \n");
    for (int k = 0; k < length; k++)
        printf("%d ", a[k]);

    return 0;
}

分析

二路归并排序的时间复杂度为$O(n\log{n})$,空间复杂度为$O(n)$。


文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
  目录