1.快速排序

2.堆排序

3.归并排序[o(n);o(nlog);稳定排序]

void MergeSort(int a[],int left,int right)

{

if(left<right){ 　　　　　　 //至少有2个元素

int mid=(left+right)/2;　　 //取中点left+(right-left)/2

MergeSort(a,left,mid);

MergeSort(a,mid+1,right);

Merge(a,b,left,mid,right); 　//合并到数组b

Copy(a,b,left,right); 　　　  //复制回数组a

}

}

void Merge(int a[],int b[],int left,int mid,int right )

{

int i=left,j=mid+1,k=left;

while((i<=mid)&&(j<=right))//当两个子序列都还有记录

if(a[i]<=a[j])

b[k++]=b[i++];

else

b[k++]=a[j++];

while(j<=right)　　　　　　//当j所指的序列中还有记录时全部拷至b

b[k++]=a[j++];

while(i<=mid)　　　　       //当i所指的序列中还有记录时全部拷至b　　

b[k++]=a[i++];

}

void Copy(int a[],int b[],int left,int right)

{

for(int i=left;i<=right;i++)

a[i++]=b[j++];

}