归并排序

Posted on | In |

分治法

该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
image

文字解释

归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；

图解

image
image

实现代码

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
using namespace std;
void MergeArray(int a[],int first,int mid,int last)
{
    int b[100],k=0;
    int i=first,j=mid+1;
    while(i<=mid&&j<=last)
    {
        if(a[i]<a[j])
            b[k++]=a[i++];
        else b[k++]=a[j++];

    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=last)
        b[k++]=a[j++];
    for(int i=0; i<k; i++)
        a[first+i]=b[i];
}
void MergeSort(int first,int last,int a[])
{
    if(first<last)
    {
        int    mid=(first+last)/2;
        MergeSort(first,mid,a);
        MergeSort(mid+1,last,a);
        MergeArray(a,first,mid,last);
        //这里也可不传mid参数
        //可写成MergeArray(a,first,last),可以在合并有序数组时算一下mid
    
    }
}
int main()
{

    int a[10]= {6,202,100,301,38,8,1};
    MergeSort(0,6,a);
    for(int i=0; i<7; i++)
        cout<<a[i]<<" ";
    return 0;
}

image

补充

归并排序它为什么会快呢？

想回答这个问题可以先想一下提高排序速度的两个重要的途径：一个是减少比较次数，一个是减少交换次数。

对于归并排序而言，我们来从之前的例子应该可以看到，两个数组的合并过程是线性时间的，也就是说我们每一次比较都可以确定出一个元素的位置。这是一个重要的性质。

我们来看一个可以用一个例子来体会一下假如有这样一个数组｛ 3，7，2，5，1，0，4，6 ｝，

冒泡和选择排序的比较次数是25次。

直接插入排序用了15次。

而归并排序的次数是相对稳定的，由我们上面提到的比较次数的计算方法，我们的例子要合并4对长度为1的，2对长度为2的，和1对长度为4的。

归并排序的最多的比较次数为4 1 + 2 3 + 7 = 17次。