归并排序

快速排序、堆排序和归并排序理论上时间复杂度为O(nlogn )，是内存占用较少的情况下，速度最快的排序算法。

当然桶排序的时间复杂度为O（n），但是需要牺牲巨大内存。

#include<iostream> using namespace std; void Merge(int a[],int f,int mid,int l,int b[]) { int s1=f,s2=mid+1; int k=f; while(s1<=mid&&s2<=l) { if(a[s1]<=a[s2]) { b[k]=a[s1]; k++; s1++; } else { b[k]=a[s2]; k++; s2++; } } while(s2<=l) { b[k]=a[s2]; k++; s2++; } while(s1<=mid) { b[k]=a[s1]; k++; s1++; } for(int i=f; i<=l; i++) a[i]=b[i]; } void Gui_sort(int a[],int f,int n,int b[]) { if(f<n) { int mid=(f+n)/2; Gui_sort(a,f,mid,b); Gui_sort(a,mid+1,n,b); Merge(a,f,mid,n,b); } } int main() { int a[5]= {3,1,5,4,2}; int b[5]; int n=4; Gui_sort(a,0,4,b); for(int i=0; i<5; i++) cout<<b[i]<<endl; return 0; }