排序算法之归并排序-蒲公英云

排序算法之归并排序

你的名字 2022-06-16 09:27 307阅读 0赞

问题描述：

输入一个原始数列，把它进行升序排序，从小到大输出。

例如：给定数列如下：
5 15 99 45 12 1 90 19 33 41

排序后的结果为：
1 5 12 15 19 33 41 45 90 99

归并排序是分之思想的典型应用，首先对N个元素进行排序是一个大的问题，我们把它对半拆分成左右两个部分，这样对N个元素排序的问题，就拆分成对【0,(N - 1)/2】和【(N - 1)/2+ 1, N -1】进行排序的子问题，如果两个子问题都解决了，我们再对两个序列进行合并，就解决了原问题，以此类推，一直分解到只有一个元素，然后再依次往上进行合并，分治思想其实就是把原问题拆分成子问题进行解决，然后把解决的结果再合并给原问题。

下标值序号： 0 1 2 3 4 5 6 7 8 9
原始状态为： 5 15 99 45 12 1 90 19 33 41
第一趟排序： (5 15) (99) (12 45) (1 90) (19) (33 41)(括号中是进行的分组)
第二趟排序： (5 15 99) (12 45) (1 19 90) (33 41)(对上一步的分组进行合并)
第三趟排序： (5 12 15 45 99) (1 19 33 41 90)
第四趟排序： (1 5 12 19 15 33 41 45 90 99)

从上面我们可以发现：

对于N个数的数列来说，归并排序是先把原数列进行分组，然后分组排好之后再进行合并
归并排序是稳定的排序，因为分组和合并的过程中，不会改变相同的数直接的顺序
归并排序划分子问题是对半分解的
在归并排序的过程中用到了一个辅助的数组
归并排序的速度虽然比快速排序要慢一点，但是他可以使用于任何进行，也就是说不管初始数列是什么，归并排序的时间复杂度都是O(nlogn)

PS：归并排序有一个非常典型的应用就是求数列的逆序数的数目，在下一篇文章中将给出算法

参考代码：

#include<stdio.h>
int arr[] = { 5, 15, 99, 45, 12, 1, 90, 19, 33, 41 };
int tmp[100];
void Merge(int s, int m, int t)
{
    int i = s, j = m + 1, k = s;
    while (i <= m && j <= t)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= m)
        tmp[k++] = arr[i++];
    while (j <= t)
        tmp[k++] = arr[j++];
}
void MergeSoft(int s, int t)
{
    int i, m;
    if (s < t)
    {
        m = (s + t) / 2;
        MergeSoft(s, m);
        MergeSoft(m + 1, t);
        Merge(s, m, t);
        for (i = s; i <= t; i++)
            arr[i] = tmp[i];
    }
}
int main()
{
    int i, nCount = sizeof(arr) / sizeof(arr[0]);
    printf("排序前\n");
    for (i = 0; i < nCount; i++)
        printf("%d ", arr[i]);
    printf("\n");
    MergeSoft(0, nCount - 1);
    printf("\n排序后\n");
    for (i = 0; i < nCount; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}