2.4 归并排序

归并排序（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));
    }
};

运行程序，输出

可以发现，待合并之前的数组是升序的，那么合并后依然是升序的，反之亦然

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);
    }
}

运行程序输出：

非递归的代码如下：

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++];
        }
    }
}

运行程序输出