排序方法（7）：归并排序

缺乏、安全感 2022-05-28 13:37 95阅读 0赞

# 归并排序 #

参考：  
[https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F][https_baike.baidu.com_item_E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F]

[http://cuijiahua.com/blog/2018/01/algorithm\_7.html][http_cuijiahua.com_blog_2018_01_algorithm_7.html]

## 一、原理 ##

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

## 二、步骤 ##

*  1、先将序列分为两组
 *  2、分别对两组进行排序
 *  3、进行归并

归并过程为：比较a\[i\]和b\[j\]的大小，若a\[i\]≤b\[j\]，则将第一个有序表中的元素a\[i\]复制到r\[k\]中，并令i和k分别加上1；否则将第二个有序表中的元素b\[j\]复制到r\[k\]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

## 三、算法实现 ##

### C语言 ###

#include <stdlib.h>
    #include <stdio.h>
    
    void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex)
    {
        int i = startIndex, j = midIndex + 1, k = startIndex;
        while (i != midIndex + 1 && j != endIndex + 1)
        {
            if (sourceArr[i] > sourceArr[j])
                tempArr[k++] = sourceArr[j++];
            else
                tempArr[k++] = sourceArr[i++];
        }
        while (i != midIndex + 1)
            tempArr[k++] = sourceArr[i++];
        while (j != endIndex + 1)
            tempArr[k++] = sourceArr[j++];
        for (i = startIndex; i <= endIndex; i++)
            sourceArr[i] = tempArr[i];
    }
    
    //内部使用递归
    void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
    {
        int midIndex;
        if (startIndex < endIndex)
        {
            midIndex = (startIndex + endIndex) / 2;
            MergeSort(sourceArr, tempArr, startIndex, midIndex);
            MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
            Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
        }
    }
    
    
    int main()
    {
        int number[] = { 0, 10, 1, 2, 8, 5, 9, 7, 3, 4, 6 };
        int i;
        int n = sizeof(number) / sizeof(number[0]);
        //int result[11] = {0};
        int *result = (int *)malloc(n * sizeof(int));
        printf("原始数据：\n");
        for (i = 0; i < n; i++)
        {
            printf("%d\t", number[i]);
        }
        printf("\n\n");
    
        MergeSort(number, result,0,n-1);
        printf("\n返回结果：\n");
        for (i = 0; i < n; i++)
        {
            printf("%d\t", result[i]);
        }
        printf("\n");
    }

### 运行结果 ###

![这里写图片描述][SouthEast]

[https_baike.baidu.com_item_E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
[http_cuijiahua.com_blog_2018_01_algorithm_7.html]: http://cuijiahua.com/blog/2018/01/algorithm_7.html
[SouthEast]: /images/20220528/23e4b8d02cf1422b920cb3f828da32df.png