经典排序算法之归并排序

#include<iostream>
using namespace std;
int *aux = NULL;
void sort(int *a,int,int);
void merge(int *a,int lo,int mid,int hi)//归并有序子数组
{
    int i =lo,j = mid+1;
    for (int k = lo;k <= hi;k++)
    {
        aux[k] = a[k];
    }
    for (int k = lo;k <= hi;k++)
    {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (aux[j]<aux[i]) a[k] = aux[j++];
        else    a[k] = aux[i++];
    }
}
void sort(int *a,int n)
{
    aux = new int[n];
    sort(a,0,n-1);
    delete[] aux;
}
//将两个子数组排序，通过归并两个字数组来将这个数组排序
void sort(int *a,int lo,int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi-lo)/2;
    sort(a,lo,mid);
    sort(a,mid+1,hi);
    merge(a,lo,mid,hi);
}
int main()
{
    int a[] = {1,2,4,3,5};
    sort(a,5);
    for (int i = 0;i < 5;i++)
    {
        cout << a[i]<< " ";
    }
    cout << endl;
    return 0;
}

首先是两两归并，然后是四四归并，然后是八八归并，一直下去！（自低向下）

#include<iostream>
using namespace std;
int *aux = NULL;
void Merge(int *a,int lo,int mid,int hi)
{
    int i = lo,j = mid+1;
    for (int k = lo;k <= hi;k++)
    {
        aux[k] = a[k];
    }
    for (int k = lo;k <= hi;k++)
    {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (aux[i]<aux[j]) a[k] = aux[i++];
        else    a[k] = aux[j++];
    }
}
void sort(int *a,int n)
{
    int N = n;
    aux = new int[N];
    for (int sz = 1;sz < N;sz = sz+sz)
    {
        for (int lo = 0;lo<N-sz;lo += sz+sz)
            Merge(a,lo,lo+sz-1,min(lo+sz+sz-1,N-1));
    }
}
int main()
{
    int a[] = {5,4,3,2,1};
    sort(a,5);
    for (int i = 0;i < 5;i++)
    {
        cout << a[i]<<" ";
    }
    cout << endl;
    return 0;
}