分治-归并排序

动画演示地址

https://visualgo.net/zh/sorting

数组排序任务可以如下完成:
1)把前一半排序
2)把后一半排序
3)把两半归并到一个新的有序数组,然后再拷贝回原数组,排序完成

用分支解决归并排序

#include <iostream>
using namespace std;

void Merge(int a[],int s,int m,int e,int tmp[])
{//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
 //归并操作时间复杂度: O(e-m+1)即O(n)
    int pb = 0;
    int p1 = s,p2 = m+1;
    while(p1<=m && p2<=e){
        if(a[p1] < a[p2])
            //p1++是将值赋给之后,要指向下一个元素
            tmp[pb++] = a[p1++];
        else
            tmp[pb++] = a[p2++];
    }
    //当两个数组比较完之后,可能其中一个数组元素比另一个多,再把多的赋给tmp[]
    while(p1<=m)
        tmp[pb++] = a[p1++];
    while(p2<=e)
        tmp[pb++] = a[p2++];
    //最后再把tmp[]中元素复制给a[],tmp[]在这个过程中作中转
    //为何是e-s+1,因为s,e不一定是开头或者末尾,如果是的话可以i<e+1;
    for(int i=0;i<e-s+1;++i)
        a[s+i] = tmp[i];
}
//从s开始到e
void MergeSort(int a[],int s, int e,int tmp[])
{
    if(s<e){
        //从中间分开,m代表中间
        int m = s +(e-s)/2; //或者int m = (s+e)/2;
        //a[]数组前一半
        MergeSort(a,s,m,tmp);
        //a[]数组后一半
        MergeSort(a,m+1,e,tmp);
        Merge(a,s,m,e,tmp);
    }
}

int a[10] = {13,27,19,2,8,12,2,8,30,89};
int b[10];

int main()
{

    int size = sizeof(a)/sizeof(int);
    //待排序的起始位置0到size-1,b是临时存储的数组,就是tmp[]
    MergeSort(a,0,size-1,b);
    for(int i=0;i<size;++i)
        cout<<a[i]<<",";
    cout<<endl;
    return 0;
}

时间复杂度