归并排序详解

水深无声 2022-07-18 08:44 114阅读 0赞

**基本概念：**

归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法，效率為O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

**归并操作（merge），指的是将两个已经排序的序列合并成一个序列的操作**。归并排序算法依赖归并操作。

**我们先来看如何归并两个有序序列，很简单：**

#include <stdio.h>
    
    void mergeArray(int a[], int n, int b[], int m, int merge[])
    {
        if (a == NULL || b == NULL)
            return ;
        int i, j, k = 0;
        /* 谁小取谁 */
        while (i <= n && j <= m) {
            if (a[i] < b[j])
                merge[k++] = a[i++];
            else
                merge[k++] = b[j++];
        }
        /* 将剩余的数据取尽 */
        while (i <= n)
            merge[k++] = a[i++];
        while (j <= m)
            merge[k++] = b[j++];
    }
    
    int main()
    {
        int a[] = {0,1,2,3,4,5,6,7,8,9,10};
        int sizea = 11;
        int b[] = {11,12,13,14,15,16,17,18,19};
        int sizeb = 9;
    
        int merge[20];
        mergeArray(a, sizea-1, b, sizeb-1, merge);
    
        int i = 0;
        for (i; i < 20; i++) {
            printf("%d ", merge[i]);
        }
        printf("\n");
    
        return 0;
    }

**运行结果：**  
![SouthEast][]

我们已经知道了怎么归并两个有序序列，**假设将待排序序列A\[0...n-1\]看成是n个长度为1的有序序列**，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。**这就是如何拆的思想。**

**所以，归并排序其实要做两件事：**  
(1) 分解：将序列每次折半拆分。  
(2) 合并：将拆分开的两个序列排序后合并。

只要理解了**归并排序的思想**，就很容易实现归并排序。

**平均时间复杂度 O(nlog n)  
最差空间复杂度 O(n)**

**效果如图：**

![20160908000104310][]

**用递归思路实现的简单例子，****先上过程图：**

![20160908095240209][]

**源码：**

#include <stdio.h>
    #include <stdlib.h>
    
    /* 合并两个排序后的数据 */
    void merge(int a[], int first, int mid, int last, int temp[])
    {
        int i = first, j = mid + 1;
    
        /* 将a[first..last] 复制到到temp[first..last]中 */
        int k;
        for (k = first; k <= last; ++k)
            temp[k] = a[k];
    
        /* 将a[first, mid]和a[mid + 1, last]有序地合并起来，放回去到a[first, last] */
        k = first;
        while (i <= mid && j <= last) {
            if (temp[i] < temp[j])
                a[k++] = temp[i++];
            else
                a[k++] = temp[j++];
        }
    
        /* 将剩余的数据取尽 */
        while (i <= mid)
            a[k++] = temp[i++];
        while (j <= last)
            a[k++] = temp[j++];
    
        /* 打印合并后的数据 */
        printf("first is:%d mid is:%d last is:%d, ", first, mid, last);
        for (i = first; i <= last; ++i)
            printf("%d ", a[i]);
        printf("\n");
    }
    
    /* 用递归思想实现 */
    void sort(int a[], int first, int last, int temp[])
    {
        if (a == NULL || temp == NULL)
            return ;
        if (first < last) {
            int mid = first + (last - first) / 2;
            sort(a, first, mid, temp); /* 将左半部分排序 */
            sort(a, mid+1, last, temp); /* 将右半部分排序 */
            merge(a, first, mid, last, temp); /* 合并两个排序后的数据 */
        }
    }
    
    int main()
    {
        int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
        int size = sizeof(arr) / sizeof(int);
        int *temp = (int *)malloc(sizeof(arr));
    
        //sort
        sort(arr, 0, size - 1, temp);
    
        //print
        int i = 0;
        for (i; i < size; ++i) {
            printf("%d\n", arr[i]);
        }
    
        free(temp);
        return 0;
    }

**编译运行：**

![SouthEast 1][]

原文出自：[http://blog.csdn.net/daiyudong2020/article/details/52464492][http_blog.csdn.net_daiyudong2020_article_details_52464492]

End;

[SouthEast]: /images/20220717/010eba33577f431e8b5e22b09bb9c5b9.png
[20160908000104310]: /images/20220717/e3211cb4a9e04d9980240fc7dc38947e.png
[20160908095240209]: /images/20220717/591e407c60ea47a992e8d771f41e4451.png
[SouthEast 1]: /images/20220717/834776c2847f44838cb46b9c0a200418.png
[http_blog.csdn.net_daiyudong2020_article_details_52464492]: http://blog.csdn.net/daiyudong2020/article/details/52464492