归并排序
归并(Merge)排序是将两个(或两个以上)有序表合并成一个新的有序表,
即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
首先考虑下如何将两个有序数列合并:
只要从比较二个数列的第一个数,谁小就先取谁,
取了后就在对应数列中删除这个数,然后再进行比较,
如果有数列为空,那直接将另一个数列的数据依次取出即可
void merge_sort(int l[],int m,int r[],int n,int a[]) { int i=0,j=0,k=0; while(i<m&&j<n){ if(l[i]<=r[j]) a[k++]=l[i++]; else a[k++]=r[j++]; } while(i<m) a[k++]=l[i++]; while(j<n) a[k++]=r[j++]; }
时间复杂度为O(n)
解决了上面的合并有序数列问题,再来看归并排序,
其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,
那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序?
可以将A,B组各自再分成二组,依次类推,当分出来的小组只有一个数据时,
可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。
这样通过先递归的分解数列,再合并数列就完成了归并排序。
void cmp(int ll,int mid,int rr) { int m=0,n=0,i,j,k; for(i=ll;i<=mid;i++) l[m++]=a[i]; for(i=mid+1;i<=rr;i++) r[n++]=a[i]; i=j=0; k=ll; while(i<m&&j<n){ if(l[i]<=r[j]) a[k++]=l[i++]; else a[k++]=r[j++]; } while(i<m) a[k++]=l[i++]; while(j<n) a[k++]=r[j++]; } void mergesort(int l,int r) { int mid; if(l<r){ mid=(l+r)/2; //不断二分 mergesort(l,mid); //左边部分 mergesort(mid+1,r); //右边部分 cmp(l,mid,r); //比较合并 } }
其时间复杂度为 O(n*log n)
归并排序的应用
归并排序最为经典的一个应用:求一个整数序列中逆序对数
设a[1...n]是一个包含n个不同数的数组,若当i<j时,有a[i] >a[j],则称(i,j)就是一个逆序对
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。