归并排序 O(N*logN) 是另一种效率很高的排序方法。"归并"的含义就是将两个或两个以上的有序表组合成一个有序表。加入两个有序表的长度分别为m、n,则一次归并的时间复杂度为O(m+n)。
我们可以用"归并"的思想来实现排序。假如待排序列含有n个关键字,则可看成是n个有序的子序列,每个序列长度为1,然后两两归并,得到[n/2]个长度为2或1的子序列,在两两归并....,知道得到一个长度为n的有序序列为止。这就是2-路归并算法。
下图就是2-路归并排序的一个例子:
#include<iostream.h>#include<malloc.h>/************************ * 归并排序 Merge Sort * ***********************/ class MergeSort{public: //递增排序 static void inc_sort(int keys[], int size);private: //归并排序算法 static void merge_sort(int raw[], int *merged, int s, int t); //归并 static void merge(int raw[], int *merged, int si, int mi, int ti);};void MergeSort:: merge(int raw[], int *merged, int si, int mi, int ti){ //把已近排序号的si-mi,mi-ti两个序列赋值给raw for(int t=si;t<=ti;t++) raw[t]=merged[t]; //归并 int i=si,j=mi+1,k=si; for(;i<=mi&&j<=ti;){ if(raw[i]<=raw[j]) merged[k++]=raw[i++]; else merged[k++]=raw[j++]; } if(i<=mi) for(int x=i;x<=mi;) merged[k++]=raw[x++]; if(j<=ti) for(int y=j;y<=ti;) merged[k++]=raw[y++];}//划分void MergeSort:: merge_sort(int raw[], int *merged, int s, int t){ if(s==t) merged[s]=raw[s]; else{ int m=(s+t)/2; MergeSort::merge_sort(raw, merged, s, m); MergeSort::merge_sort(raw, merged, m+1,t); MergeSort::merge(raw, merged, s,m,t); }}void MergeSort:: inc_sort(int keys[],int size){ int * merged=(int *)malloc(size*sizeof(int)); MergeSort::merge_sort(keys,merged,0,size-1); //打印排序结果 for(int i=0;i<size;i++) cout<<merged[i]<<" "; cout<<endl; free(merged);}//Test MergeSortvoid main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); MergeSort::inc_sort(raw,size); }
代价分析:
上图可以看出,一个N关键字的序列,两两归并可以构造一棵高度为[logN]的归并排序树。而每一次归并的时间复杂度为O(m+n)。因此每一趟归并的时间复杂度为O(N),如上图。归并排序算法的总时间复杂度为O(N*logN) 。其所需要的辅助空间就是一个能容纳中间合并结果的数量为N的连续空间。因此空间复杂度为O(N) 。是稳定排序方法 。
联系客服