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++];
}