归并排序

递归实现归并排序：

void merge_sort(int *a, int l, int r){
    int mid = (l+r)/2;

    //若只有一个元素，返回上一层（有两个元素）
    if(r-l == 0) return ;

    //不断分成左右两边
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);

    int k = 0;
    int l_i = l,r_i=mid+1;

    //把左右两个子序列按顺序放到tmp里（不用tmp的话会导致左半边元素被覆盖）
    int * tmp = new int[r-l+1];
    while(l_i <= mid && r_i <= r){
        if(a[l_i]<=a[r_i]) tmp[k] = a[l_i++];
        else tmp[k] = a[r_i++];
        ++k;
    }
    //若其中一个没排完，把剩下的元素补进tmp
    while(l_i <= mid) tmp[k++] = a[l_i++];
    while(r_i <= r) tmp[k++] = a[r_i++];

    for(int i = l, j = 0; i <= r; i++, j++){
        a[i] = tmp[j];
    }
    delete tmp;
}

完整代码

在线测试运行结果：click

#include <iostream>
using namespace std;

void merge_sort(int *a, int l, int r){
    int mid = (l+r)/2;

    //若只有一个元素，返回上一层（有两个元素）
    if(r-l == 0) return ;

    //不断分成左右两边
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);

    int k = 0;
    int l_i = l,r_i=mid+1;

    //把左右两个子序列按顺序放到tmp里（不用tmp的话会导致左半边元素被覆盖）
    int * tmp = new int[r-l+1];
    while(l_i <= mid && r_i <= r){
        if(a[l_i]<=a[r_i]) tmp[k] = a[l_i++];
        else tmp[k] = a[r_i++];
        ++k;
    }
    //若其中一个没排完，把剩下的元素放进tmp
    while(l_i <= mid) tmp[k++] = a[l_i++];
    while(r_i <= r) tmp[k++] = a[r_i++];

    for(int i = l, j = 0; i <= r; i++, j++){
        a[i] = tmp[j];
    }
    delete tmp;
}

int main()
{
    int a[] = {2,4,1,6,8,5,3,7};
    int n = sizeof(a)/sizeof(a[0]);
        merge_sort(a,0,n-1);
    for(auto s:a){
        cout << s << ' ';
    }
    return 0;
}