归并排序：算法时间复杂度O(nlogn) 空间复杂度O(n)
算法实现
#include <iostream>
using namespace std;
void merge(int * a, int start, int mid, int end)
{
int i = start, j = mid + 1;
int m = mid, n = end;
int tmp[20];
int k = 0;
while(i <= m && j <= n)
{
if(a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while(i <= m)
tmp[k++] = a[i++];
while(j <= n)
tmp[k++] = a[j++];
for(int i = 0; i < k; ++i)
a[start+i] = tmp[i];
}
void mergeSort(int * a, int start, int end)
{
if(start < end)
{
int mid = (start+end)/2;
mergeSort(a, start, mid);
mergeSort(a, mid+1, end);
merge(a, start, mid, end);
}
}
int main()
{
int a[10] = {52,12,36,14,48,69,57,89,45,16};
mergeSort(a, 0, 9);
for(int i = 0; i < 10; ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
