排序算法六——归并排序

比眉伴天荒 2022-06-10 04:40 150阅读 0赞

\*\*

## **算法排序六：归并排序** ##

\*\*  
归并排序，很简单，就是写两个函数（函数1跟函数2），函数1是干嘛的呢？函数1的功能主要就是把传进来的一组数给他从中间分成两组，而函数2的功能就是把两组数字合并到一起并排好序。  
看图：  
![这里写图片描述][SouthEast]  
比如这张图片上的这组数字，最左边是left，最右边是right。我从中间劈开，（mid就是（left + right）/2） 劈开之后，就是两组数了，左边那组数字left还是原来的left，但它的right就变成了mid，右边这组数字的left就变成了mid + 1，right还是原来的right。 然后我们再调用这个函数，把那两组数分别从中间劈开，然后再劈开，劈，劈…… 到最后就劈的不能再劈了，只剩一个数了。这个时候，函数2开始闪亮登场，把劈开的数字按照顺序放到一个临时数组里面，再把临时数组里面的数给我原来要排序的数组。（这句话写的我自己都很迷糊，看了代码之后就能看懂这句话了）。  
比如图上面的一组数字：\{2,9,1,0,7,4,8,5,3,6\}. 程序刚开始把他劈成\{2，9，1，0，7\}跟\{4，8，5，3，6\}两组，然后递归调用函数1，把\{2，9，1，0，7\}再劈开成\{2，9，1\}跟\{0，7\}两组数，然后再递归调用函数1，把\{2，9，1\}劈开成\{2\}跟\{9，1\}两组数字，\{2\}已经不能再劈l，只能劈\{9，1\}，劈成\{9\}跟\{1\}，这个时候调用函数2开始归并，\{1，9\}->\{1，2，9\}，所以第一趟排序结果应该是\{1，2，9，0，7，4，8，5，3，6\}。  
剩下的就自己劈吧！  
看看代码，代码注释的比较清楚

/***************************************************** File name:6merge_sort.c Author: Tang Zhiqian Date:2017-08-09 15:37 *****************************************************/
    
    #include <stdio.h>
    
    #define MAX 10
    
    typedef int ElementType;
    typedef ElementType ARR[MAX];
    ARR arr = {
       2,9,1,0,7,4,8,5,3,6};
    
    void merge_sort(ARR arr,int left,int right);   //将数字从中间分开成两组数字
    void merge(ARR arr,int left,int mid,int right);   //归并
    void print(ARR arr);
    
    
    int main()
    {
        merge_sort(arr,0,MAX - 1);
        //print(arr);
    
        return 0;
    }
    
    
    void merge(ARR arr,int left,int mid,int right)    //将分开的数字排好序再归并
    {
        int len = (right - left) + 1;    //长度
        ElementType temp[len];    //定义一个临时数组来存合并后的数
        int i = left;
        int j = mid + 1;
        int k = 0;
    
        while(i <= mid && j <= right)  //i从left到mid，j从mid+1到right
        {
            if (arr[i] < arr[j])
            {
                temp[k++] = arr[i++];  //谁小就把谁存到临时数组里面，然后指针i或j往后移动一位
            }
            else
            {
                temp[k++] = arr[j++];
            }
        }
    
        //运行到这一步，说明i和j其中有一个已经全部放到临时数组里面了，
        while(i <= mid)   //判断是i还是j没排完，没排完的往后接上。
        {
            temp[k++] = arr[i++];
        }
        while(j <= right)
        {
            temp[k++] = arr[j++];
        }
    
        for (i = 0; i < len; i++)    //把临时数组里面的数字赋值给原来的数组arr
        {
            arr[i + left] = temp[i];
        }
    
        print(arr);
    }
    
    void merge_sort(ARR arr,int left,int right)
    {
        if(left == right)    //递归调用的结束条件
        {
            return;
        }
        int mid = (left + right)/2;   //中间值
    
        merge_sort(arr,left,mid);    //给左半边分成两组（递归调用）
        merge_sort(arr,mid + 1,right);    //给右半边分成两组（递归调用）
        merge(arr,left,mid,right);    //分完之后排序，归并
    }
    
    
    void print(ARR arr)
    {
        int i;
        for (i = 0; i < MAX; i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }

运行结果：  
![这里写图片描述][SouthEast 1]

果然第一躺排序结果是：1 2 9 0 7 4 8 5 3 6.  
归并排序是通过比较移动的，没有跳跃性的移动，是稳定的排序。  
时间复杂度O（n+logn）。但是空间复杂度就比较大，因为它需要每次申请一个数组来存归并的数字，也就是说，归并排序是一种占用空间，效率高的稳定排序！  
美滋滋！

[SouthEast]: /images/20220610/537167d5f6ac4478b8ad779ec4218104.png
[SouthEast 1]: /images/20220610/ae002d93a6cd43b48ebec48c8647b7ac.png