排序算法之归并排序

归并排序（Merge Sort）

归并排序是利用归并的思想实现排序的方式，该算法采用的是经典的分治算法

归并排序过程

• 将n个元素从中间切开，分成两部分。（左边可能比右边多1个数）
• 将步骤1分成的两部分，再分别进行递归分解。直到所有部分的元素个数都为1。
• 从最底层开始逐步合并两个排好序的数列。

归并排序过程

归并排序动图

归并排序过程

归并排序代码（递归）

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int a[10] = {33, 12, 15, 1, 5, 9, 48, 4, 13, 19};

void mergeArray(int *a, int first, int mid, int end, int *temp)
{
    int i = first, j = mid + 1;
    int m = mid, n = end;
    int k = 0;
    while(i <= m && j <= n)
    {
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while(i <= m) temp[k++] = a[i++];
    while(j <= n) temp[k++] = a[j++];
    for(int l=0; l<k; ++l) a[first + l] = temp[l];
}

void mergeSort(int *a, int first, int end, int *temp)
{
    if(first < end)
    {
        int mid = (first + end) / 2;
        mergeSort(a, first, mid, temp);
        mergeSort(a, mid + 1, end, temp);
        mergeArray(a, first, mid, end, temp);
    }
}

void sort(int *b)
{
    int temp[10];
    mergeSort(b, 0, 9, temp);
}


int main()
{
    for(int i=0; i<10; ++i) cout<<a[i]<<" ";
    cout<<endl;
    
    sort(a);
    
    for(int i=0; i<10; ++i) cout<<a[i]<<" ";
    cout<<endl;
}

归并排序复杂度

时间复杂度：
空间复杂度：