归并排序是利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。归并排序中,“归”代表的是递归的意思,即递归的将数组折半的分离为单个数组,例如数组:[2,6,1,0],会先折半,分为[2,6]和[1,0]两个子数组,然后再折半将数组分离,分为[2]、[6]和[1]、[0]。“并”就是将分开的数据按照从小到大或者从大到小的顺序在放到一个数组中。如上面的[2]、[6]合并到一个数组中是[2,6],[1]、[0]合并到一个数组中是[0,1],然后再将[2,6]和[0,1]合并到一个数组中即为[0,1,2,6]。
归并排序算法的原理如下:对于给定的一组记录(假设共有n个记录),首先将每两个相邻的长度为1的子序列进行归并,得到n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列。
所以,归并排序的关键就是两步:第一步,划分半子表;第二步,合并半子表。以数组{49,38,65,97,76,13,27}为例,归并排序的具体步骤如下:
初始关键字:
一趟归并后:
二趟归并后:
三趟归并后:[13 27 38 49 65 76 97]
程序示例如下:
public class Test{
public static void Merge(int array[], int p, int q, int r){
int i, j, k, n1, n2;
n1=q-p+1;
n2=r-q;
int[]L=new int[n1];
int[]R=new int[n2];
for(i=0, k=p; i<n1; i++, k++)
L[i]=array[k];
for(i=0, k=q+1; i<n2; i++, k++)
R[i]=array[k];
for(k=p, i=0, j=0; i<n1&&j<n2; k++){
if(L[i]>R[j]){
array[k]=L[i];
i++;
}
else{
array[k]=R[j];
j++;
}
}
if(i<n1){
for(j=i; j<n1; j++, k++)
array[k]=L[j];
}
if(j<n2){
for(i=j; i<n2; i++, k++)
array[k]=R[i];
}
}
public static void MergeSort(int array[], int p, int r){
if(p<r){
int q=(p+r)/2;
MergeSort(array, p, q);
MergeSort(array, q+1, r);
Merge(array, p, q, r);
}
}
public static void main(String[]args){
int i=0;
int a[]={5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
int len=a.length;
MergeSort(a, 0, len-1);
for(i=0; i<len; i++)
System.out.print(a[i]+"");
}
}
程序运行结果为:
9 8 7 6 5 4 3 2 1 0
二路归并排序的过程需要进行logn趟。每一趟归并排序的操作,就是将两个有序子序列进行归并,而每一对有序子序列归并时,记录的比较次数均小于等于记录的移动次数,记录移动的次数均等于文件中记录的个数n,即每一趟归并的时间复杂度为O(n)。因此,二路归并排序的时间复杂度为O(nlogn)。