浅谈归并排序

素颜马尾好姑娘i 2022-08-23 05:48 118阅读 0赞

昨晚睡前看了下刘汝佳紫书上关于归并排序的介绍，很想自己实现一遍，于是趁着今天下午复习马基的时间自己手动敲了一遍代码。由于之前有快排的经验，所以这次理解起归并排序并不十分困难。  
先上自己写的代码：

void merge_sort(int num[], int left, int right, int temp[])
    {
        if (left == right)
            return;
        int l = left;
        int i = left;
        int mid = left + (right - left) / 2;
        int r = mid + 1;
        merge_sort(num, left, mid, temp);
        merge_sort(num, mid+1, right, temp);
        while (l <= mid && r <= right)
        {
            if (num[l] < num[r])
                temp[i++] = num[l++];
            else
                temp[i++] = num[r++];
        }
        while (l <= mid)
            temp[i++] = num[l++];
        while (r <= right)
            temp[i++] = num[r++];
        for (int j = left; j <= right; ++j)
            num[j] = temp[j];
    }

其实归并的思想和快排比较相似，两者都是分而治之。快排主要思路是先找一个基准数，把所有比这个数小的数放在基准数的一变，比它大的放在另一边，但并不要求放的时候要按顺序来，然后利用递归将左边部分和右边部分分别采用同一方法排，最后通过多次调用递归肯定能够将这些数按顺序排好。  
而归并呢？归并就是先找一个中间点，两边的数都是按顺序排好了的。这时候有一个另外的数组用来按顺序安放这两边的数。  
也就是说，分别从左到右遍历两边的数，每次把数字放在第二个数组中前先比较左边和右边的数的大小，然后决定放哪个。当某一边已经放完的时候就退出循环，开始将剩余一边的数按顺序放进第二个数组（这时候剩余这边的数肯定都比第二个数组中的数大或小，否则之前比较的时候就已经放进去了）。然后把这些已经排好的数按顺序归还给原来的数组。不知道你注意到一个问题没？怎么样实现将中间数两边的子数组进行排序。这里又要用到递归了。每次在把数组中的数放到第二个数组中之前先把左右两边的数分别进行排序。为了防止无限递归，我们在函数前面加上if(left<=right)这个条件来判断是否终止此函数（可以思考下如果将<=换成<是否可行），跳回上一层。如果跳回了上一层递归，就可以开始进行把数有条件的交给第二个数组，然后第二个数组把数归还给原来的数组了。其实第一次跳回上一层递归时原数组只有两个元素，否则将会发生它下一个递归并不能直接返回，而是它的递归还有递归，这与它是第一次跳回的递归矛盾了。这就是归并排序名字的由来。一直递归到底层，然后不断地将许许多多的子数组合并回原来的数组，最终实现归并排序的正确性。  
可以看出，快速排序和归并排序最本质的区别是快速排序是先将顶层的数处理好在再利用递归去处理两边的子数组；而归并排序的本质是先将最底层的数排好然后回来合并排好。

之后又做了个关于快排和归排的速度测试，结果是五次测试都是归排完爆快排。之前有看过一篇关于快排和归排的文章，今天我特地将我的归排和他的归排比较了一下，结果是我的略快一点；但是当我把我的快排和他的快排比较的时候，发现我的快排比他的快很多，所以排法的快慢是看你的实现方式的，即使是同一种排序方法，实现方式不同也会造成速度上很大的差距。