Java编程中实现归并排序算法的实例教程
算法概述/思路
归并排序是基于一种被称为“分治”(divideandconquer)的策略。其基本思路是这样的:
1.对于两个有序的数组,要将其合并为一个有序数组,我们可以很容易地写出如下代码:
//bothaandbisascend. publicvoidmerge(int[]a,int[]b,int[]c){ inti=0,j=0,k=0; while(i<=a.length&&j<=b.length){ if(a[i]<=b[i]){ c[k++]=a[i++]; } else{ c[k++]=b[j++]; } } while(i<=a.length){ c[k++]=a[i++]; } while(j<=b.length){ c[k++]=b[j++]; } }
容易看出,这样的合并算法是高效的,其时间复杂度可达到O(n)。
2.假如有一个无序数组需要排序,但它的两个完全划分的子数组A和B分别有序,借助上述代码,我们也可以很容易实现;
3.那么,如果A,B无序,怎么办呢?可以把它们再分成更小的数组。
4.如此一直划分到最小,每个子数组都只有一个元素,则可以视为有序数组。
5.从这些最小的数组开始,逆着上面的步骤合并回去,整个数组就排好了。
总而言之,归并排序就是使用递归,先分解数组为子数组,再合并数组。
例子
下面举例说明,假如要对数组a={2,1,3,5,2,3}进行排序,那么把数组划分为{2,1,3}和{5,2,3}两个子数组,这两个子数组排序后变为{1,2,3}和{2,3,5},然后对这两个数组进行归并操作便得到最终的有序数组。代码实现如下:
voidsort(int[]a){ int[]aux=newint[a.length];//辅助数组 mergeSort(a,0,a.length-1,aux); } voidmergeSort(int[]a,intlo,inthi,int[]aux){ if(hi<=lo) return; intmid=lo+(hi-lo)/2; mergeSort(a,lo,mid,aux); mergeSort(a,mid+1,hi,aux); merge(a,lo,mid,hi,aux); } voidmerge(int[]a,intlo,intmid,inthi,int[]aux){ inti=lo,j=mid+1; for(intk=lo;k<=hi;k++){ aux[k]=a[k]; } for(intk=lo;k<=hi;k++){ if(i>mid) a[k]=aux[j++]; elseif(j>hi) a[k]=aux[i++]; elseif(aux[i]<=aux[j]) a[k]=aux[i++]; else a[k]=aux[j++]; } }
另一种实现:自底向上的归并排序
在上面的实现中,相当于将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。将一个大的数组的排序划分为小数组的排序是自顶向下的排序。还有一种实现是自底向上的排序,即先两两归并,然后四四归并......代码实现如下:
voidsort(int[]a){ intN=a.length; int[]aux=newint[N]; for(intsz=1;sz<N;sz+=sz){ for(intlo=0;lo<N-sz;lo+=sz+sz){ //在每轮归并中,最后一次归并的第二个子数组可能比第一个子数组要小 merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1),aux); } } }