排序算法:归并排序

归并排序的核心:分治思想

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

图片由CobaltBlue - en.wikipedia,CC BY-SA 2.5链接
归并排序-维基百科,自由的百科全书

上一篇关于快排和插排的文章中我们讲了分治思想,在这里不在重复其概念。
在这里我们按照分治模式分解一下归并排序
-分解:将n个元素组成的数组切分成两个数组,每个数组包含n/2个元素
-解决:对两个数组递归的进行排序
-合并:合并两个已排序的数组,得到最终结果

归并排序和快排的区别和联系

最大的区别便在于第一步分解,快排的分解是需要将其划分成两个子集,使得左边的子集中的所有元素都是小于主元,右边的子集中的所有元素都是大于主元的,而归并排序则是随意的,只需要使得两个子集元素数量相等即可。(如果元素个数为奇数,那么把一个元素加到任意一个集合中都行)
简单的来说,快排的重点在于分解,而归并排序的重点在于合并,两种排序的图解已经清晰的解释了这一点。
快速排序:

图片由en User:RolandH,CC BY-SA 3.0

归并排序:
Merge-sort-example-300px.gif
图片由Swfung8CC BY-SA 3.0链接

归并排序分解的实现

emmm,这个没啥好讲的,归并排序的分解直接从中间切一刀就可以了。

int P = start + ((end - start) >> 1);

这里之所以用这种方式找中间元素是为了防止当两个数都很大的时候溢出,使用位运算是因为位运算更高效。

归并排序解决的实现

这里用的递归,也没啥好讲的,不理解的可以去看我之前写的关于递归的文章。

        gbsort(nums, start, P);
        gbsort(nums, P + 1, end);

简单讲一下的话,这里就相当于是叫了两个小弟,让第一个小弟去吧左边排好序,第二个小弟去把右边排好序列。
至于如何实现,你管他怎么实现,递归求解最忌讳的就是去思考细节,局部,只要其范围在逐渐缩小,那么小到一定范围自然就有解了。

归并排序合并的实现

这里才是归并排序的核心。
呐,经过了上面两个步骤,我们得到了排好序的两个数组。那么我们要如何合并成一个数组呢?
举个例子:
这是我们排好序的两个数组
注意:这里说的两个数组只是为了方便理解,实际上,两个数组是通过指针分出来的,并不是开辟了两个数组!!!


首先,开辟一个辅助数组,然后将原数组的内容复制过去。
一开始左指针和右指针分别指向两个已排序数组的起点。还需要一个指针指示复制的位置。
然后判断左右指针指向的值,谁小就复制谁到原数组中复制指针指向的位置。等于则复制谁都一样,然后该指针和复制指针前移。

谁便选一个,复制到原数组然后右移

重复以上步骤

2小,所以把2复制到复制指针那里。右移。

重复以上步骤

4小,所以把4复制到复制指针那里。右移。

重复以上步骤

7小,所以把7复制到复制指针那里。右移。
此时,左指针越界了,结束。
尽管右指针没有到达末尾,但是我们发现数组依然排好了序列。
所以对于右指针没有达到末尾,我们大可以不管他,那,左指针没有达到中点呢?

对于这种情况,我们就需要将左指针到中点的元素移动到复制指针后面。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
struct print
{
    void operator()(int n)//定义用于打印的一元谓词
    {
        cout << n << " ";
    }
};

vector<int>temp;//在递归外定义全局变量,避免每次递归都开辟数组
void hb(vector<int> & nums, int start, int end, int P)
{
    temp.assign(nums.begin(), nums.end());//新建辅助数组,复制待排序数组的值
    int zp = start;//左起点指针
    int yp = P + 1;//右起点指针
    int cp = start;//复制指针
    while (zp <= P && yp <= end)
    {
        if (temp[zp] <= temp[yp])
        {
            nums[cp] = temp[zp];
            cp++;
            zp++;
        }
        else
        {
            nums[cp] = nums[yp];
            cp++;
            yp++;
        };
    }
    while (zp <= P)//之所以要判断这样做是因为存在一种情况,yp达到边界而zp还没达到边界所以需要把剩余的元素添加到cp之后
    {
        nums[cp] = temp[zp];
        cp++;
        zp++;
    }


}
void gbsort(vector<int> & nums, int start, int end)
{
    if (start < end)
    {
        int P = start + ((end - start) >> 1);
        gbsort(nums, start, P);
        gbsort(nums, P + 1, end);
        hb(nums, start, end, P);
    }


}
int main()
{
    vector<int>in;
    srand(time(0));
    int T = rand() % 20;
    for (int i = 0; i < T; i++)
    {
        in.push_back(rand() % 200);//生成随机数组
    }
    gbsort(in, 0, in.size() - 1);
    for_each(in.begin(), in.end(), print());//使用算法库函数调用一元谓词打印一元数组内容
    return 0;
}

运行结果

Last modification:May 29th, 2019 at 04:00 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment