归并排序（Merge Sort）是分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列之间有序。将两个有序数组合并成一个有序数组，称为二路归并(binary merge)。
之前讲解的冒泡排序，选择排序，插入排序都是时间复杂度都是O(N2)，而归并排序只需要O(N*logN)，效率比前三种算法提升很多。
归并排序的思想：
将一个数组拆分成两半，分别对每一半进行排序，然后使用合并(merge)操作，把两个有序的子数组合并成一个整体的有序数组。我们可以把一个数组刚开始先分成两，也就是2个1/2，之后再将每一半分成两半，也就是4个1/4，以此类推，反复的分隔数组，直到得到的子数组中只包含一个数据项，这就是基值条件，只有一个数据项的子数组肯定是有序的。
二路归并
归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个数组C，数组C包含数组A和B的所有数据项，并且使它们有序的排列在数组C中。首先我们来看看归并的过程，然后看它是如何在排序中使用的。
假设有两个有序数组，不要求有相同的大小。设数组A有4个数据项，数组B有6个数据项，它们要被归并到数组C中，开始时数组C有10个存储空间，归并过程如下图所示：
归并前：
归并后：
在这个图中，带圈的数字显示了把A和B中的数据项转移到数组C中的顺序
首先，我们需要注意的是需要合并的有序数组A和B都是升序的，在二路归并中，要合并的两个有序数组必须都是升序或者降序，即方向必须一致，这样可以简化我们在合并过程中的处理。
在合并时，从两个数组中，任选一个，假设是A：
第一轮比较：先用A[0]与B[0]比较，把较小的放入值放入C[0]中(因为是升序)，因此B[0]<A[0]，所以将C[0]=B[0]=7
第二轮比较：用A[0]与B[1]比较，把较小的放入值放入C[1]中(因为是升序)，因此B[1]<A[0]，所以将C[1]=B[1]=14
第三轮比较：用A[0]与B[2]比较，把较小的放入值放入C[2]中(因为是升序)，因此B[2]>A[0]，所以将C[2]=A[0]=23
第四轮比较：用A[1]与B[2]比较，把较小的放入值放入C[3]中(因为是升序)，因此B[2]>A[1]，所以将C[3]=B[2]=39
...
可以看出来，比较的原则很简单，就是将A中的数字与B中的数组进行比较，例如将A[m]与B[n]进行比较，将较小的数字放入C中下一个可以存放的位置， 假设A[m]<B[n]，那么就是将A[m]放入C中，那么下一次比较时，就需要使用A[m+1]与B[n]比较；反之则用A[m]与B[n+1]进行比较，不断的循环次过程。
如果一个数组中的数字都放完了之后，例如上例中，B数组已经都放入C中了，但是A数组还有两个元素没有放入，此时B已经没有元素可以继续与A进行比较，不过，此时已经没有继续比较的必要的，因为是我们是按照从小到大的顺序将数字放入C中，当B放完了，而A还没有放完，那就说明A中剩余的元素必然都比B最大的元素大，因此只需要将A中剩余没有比较的元素，按照顺序依次放入C中即可
public class TwoWayMerge {
/**
* 将两个有序数组，返回一个合并成后的大的有序数组，如果两个小数组是降序的，那么合并后依然是降序；反之亦然
* @param firstArray
* @param secondArray
* @param asc 表示这两个数组是升序数组还是降序数组
*/
public static int[] merge(int[] firstArray,int[] secondArray,boolean asc) {
//创建一个临时数组，其大小等于两个要合并的数组的大小
int[] resultArray=new int[firstArray.length+secondArray.length];
//创建三个变量，分别表示三个数组当前迭代到的下标的位置
int firstArrayIndex = 0, secondArrayIndex = 0, resultArrayIndex = 0;
// firstArray secondArray同时进行迭代，在都没有迭代完的情况下，继续，否则跳出
while (firstArrayIndex < firstArray.length && secondArrayIndex < secondArray.length) {
if(asc){//升序
if (firstArray[firstArrayIndex] < secondArray[secondArrayIndex]){
resultArray[resultArrayIndex++] = firstArray[firstArrayIndex++];
}else{
resultArray[resultArrayIndex++] = secondArray[secondArrayIndex++];
}
}else{//降序
if (firstArray[firstArrayIndex] > secondArray[secondArrayIndex]){
resultArray[resultArrayIndex++] = firstArray[firstArrayIndex++];
}else{
resultArray[resultArrayIndex++] = secondArray[secondArrayIndex++];
}
}
}
// secondArray所有元素已经迭代结束,但是firstArray没有迭代完，将firstArray的剩余元素直接拷贝到resultArray的后面
while (firstArrayIndex < firstArray.length){
resultArray[resultArrayIndex++] = firstArray[firstArrayIndex++];
}
// secondArray所有元素已经迭代结束,但是firstArray没有迭代完,将secondArray的剩余元素直接拷贝到resultArray的后面
while (secondArrayIndex < secondArray.length){
resultArray[resultArrayIndex++] = secondArray[secondArrayIndex++];
}
return resultArray;
}
public static void main(String[] args) {
//准备2个待合并升序数组进行合并
int[] firstArray = {1,3,5,7};
int[] secondArray = {3,4,6,7};
System.out.println("待合并升序数组:\n"+(Arrays.toString(firstArray)+"\n" + Arrays.toString(secondArray)));
int[] resultArray = merge(firstArray, secondArray,true);
System.out.println("合并后:\n" + Arrays.toString(resultArray));
System.out.println();
//准备2个待合并降序数组进行合并
firstArray = new int[]{9,6,3,0};
secondArray =new int[] {10,5,3,-1};
System.out.println("待合并降序数组:\n"+(Arrays.toString(firstArray)+"\n" + Arrays.toString(secondArray)));
resultArray = merge(firstArray, secondArray,false);
System.out.println("合并后:\n" + Arrays.toString(resultArray));
}
};运行程序，输出
待合并升序数组: [1, 3, 5, 7] [3, 4, 6, 7] 合并后: [1, 3, 3, 4, 5, 6, 7, 7] 待合并降序数组: [9, 6, 3, 0] [10, 5, 3, -1] 合并后: [10, 9, 6, 5, 3, 3, 0, -1] |
可以发现，待合并之前的数组是升序的，那么合并后依然是升序的，反之亦然
merge方法中有3个while循环：
第一个循环：
用于同时迭代firstArray和secondArray，比较他们的数据项，并且把较小(或者较大)的数据项复制到resultArray中。在firstArray和secondArray都没有迭代完时，循环继续，否则，跳出循环。
当跳出循环时，可能是firstArray迭代完了，econdArray没有迭代完；也有可能是相反的情况，因此有了第二个循环和第三个循环
第二个循环：
用于处理secondArray所有元素已经迭代结束,但是firstArray没有迭代完的情况，将firstArray的剩余元素直接拷贝到resultArray中
第三个循环：
用于处理firstArray所有元素已经迭代结束,但是secondArray没有迭代完的情况 ,将secondArray的剩余元素直接拷贝到resultArray中
归并排序递归实现
递归算法的实现代码如下：
public class RecMergeSort {
public static void mergeSort(int[] data,int left,int right){ //left,right均为数字元素下标
if(left<right){
int half=(left+right)/2;
mergeSort(data,left,half);
mergeSort(data,half+1,right);
merge(data,left,right);
}
}
public static void merge(int [] array,int startIndex,int endIndex){
int mid=(startIndex+endIndex)/2;
int leftStartIndex=startIndex;
int rightStartIndex=mid+1;
int count=0;
int temp[]=new int[endIndex-startIndex+1];
while(leftStartIndex<=mid&&rightStartIndex<=endIndex){
if(array[leftStartIndex]<array[rightStartIndex]){
temp[count++]=array[leftStartIndex++];
}else{
temp[count++]=array[rightStartIndex++];
}
}
while(leftStartIndex<=mid){
temp[count++]=array[leftStartIndex++];
}
while(rightStartIndex<=endIndex){
temp[count++]=array[rightStartIndex++];
}
count=0;
while(startIndex<=endIndex){
array[startIndex++]=temp[count++];
}
}
public static void printArray(int arr[]){
for(int k=0;k<arr.length;k++){
System.out.print(arr[k]+"\t");
}
}
public static int[] getArray(){
// int[] data={4,2,3,1};
int[] data={543,23,45,65,76,1,456,7,77,88,3,9};
return data;
}
public static void main(String args[]){
int[]a=getArray();
System.out.print("数组排序前：");
printArray(a);
System.out.print("\n");
mergeSort(a,0,a.length-1);
System.out.print("归并排序后：");
printArray(a);
}
}运行程序输出：
数组排序前：543 23 45 65 76 1 456 7 77 88 3 9 归并排序后：1 3 7 9 23 45 65 76 77 88 456 543 |
非递归的代码如下：
public class WhileMergeSort {
public static void main(String args[]){
int[] array = new int[]{1,5,6,8,9,4,3};
System.out.println("OriginalArray:" + Arrays.toString(array));
mergeSort(array);
System.out.println("SortedArray:" + Arrays.toString(array));
}
public static void mergeSort(int[] array){
int len = 1;
while(len < array.length){
for(int i = 0; i < array.length; i += 2*len){
merge(array, i, len);
}
len *= 2;
}
}
public static void merge(int[] array, int startIndex, int endIndex){
int leftStartIndex = startIndex;
int leftHalfLength = startIndex + endIndex;//归并的前半部分数组
int rightStartIndex = startIndex + endIndex;
int rightHalfLength = rightStartIndex +endIndex;//归并的后半部分数组
int[] temp = new int[2*endIndex];
int count = 0;
while(startIndex < leftHalfLength && rightStartIndex < rightHalfLength && rightStartIndex < array.length){
if(array[startIndex] <= array[rightStartIndex]){
temp[count++] = array[startIndex++];
}
else{
temp[count++] = array[rightStartIndex++];
}
}
while(startIndex < leftHalfLength && startIndex < array.length){//注意：这里i也有可能超过数组长度
temp[count++] = array[startIndex++];
}
while(rightStartIndex < rightHalfLength && rightStartIndex < array.length){
temp[count++] = array[rightStartIndex++];
}
count = 0;
while(leftStartIndex < rightStartIndex && leftStartIndex < array.length){
array[leftStartIndex++] = temp[count++];
}
}
}运行程序输出
| OriginalArray:[1, 5, 6, 8, 9, 4, 3] SortedArray:[1, 3, 4, 5, 6, 8, 9] |
