归并排序————o(nlogn)

归并排序：

与选择排序等相比，归并排序的时间复杂度是o(nlogn)，且是稳定的。 原理：将所排序序列分成两个子序列，递归调用函数将子序列排好序后，再合并。 不足：需要一个额外的数组用于合并，造成空间的浪费。 C语言实现

int extraArry[100000]; int cmp(int element1,int element2){//比较 return element1-element2; } void Merge_Sort(int *numSequence,int start,int end){ int i,mid=(start+end)/2,j,k; if(end-start<=1)return;//递归的基本情况 else{ Merge_Sort(numSequence,start,mid); //子序列排序 Merge_Sort(numSequence,mid,end); for(i=start,j=start,k=mid;i<end&&j<mid&&k<end;i++){//合并子序列 if(cmp(numSequence[j],numSequence[k])>0){//extraArry用于合并过程中临时储存 extraArry[i]=numSequence[k++]; } else{ extraArry[i]=numSequence[j++]; } } while(j!=mid)extraArry[i++]=numSequence[j++]; while(k!=end)extraArry[i++]=numSequence[k++]; for(i=start;i<end;i++)numSequence[i]=extraArry[i]; } }