归并排序算法（Java实现）

向右看齐 2022-06-06 01:38 230阅读 0赞

**1、基本思想**

归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序的时间复杂度是O(N\*lgN)。

**2、工作原理**

归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括”从上往下”和”从下往上”2种方式。

下面的图片很清晰的反映了”从下往上”和”从上往下”的归并排序的区别。

![这里写图片描述][SouthEast]

**从下往上的归并排序：**将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并，得到若干个长度为2的有序数列，再将这些数列两两合并，得到若干个长度为4的有序数列，再将它们两两合并，直接合并成一个数列为止。这样就得到了我们想要的排序结果。

![这里写图片描述][SouthEast 1]

**从上往下的归并排序**：它与”从下往上”在排序上是反方向的。它基本包括3步：

1.  分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2;
2.  求解：递归地对两个子区间a\[low…mid\] 和 a\[mid+1…high\]进行归并排序。递归的终结条件是子区间长度为1。
3.  合并：将已排序的两个子区间a\[low…mid\]和 a\[mid+1…high\]归并为一个有序的区间a\[low…high\]。

![这里写图片描述][SouthEast 2]

**3、Java实现**

/** * @Comment 归并排序算法 * @Author Ron * @Date 2017年10月26日 下午2:56:33 * @return */
    public class MergeSort { 
    
        /** * @Comment 合并子序列 * @Author Ron * @Date 2017年10月26日 下午5:08:11 * @param sources 待排序的数组 * @param start 第一个子序列起始位置 * @param mid 第一个子序列结束位置，第二个子序列起始位置 * @param end 第二个子序列结束位置 * @return */
        static void merge(int[] sources,int start,int mid,int end){
            int[] temp = new int[end-start+1];//汇总两个序列的临时区域
            int i = start;
            int j = mid+1;
            int k=0;
    
            while (i <= mid && j <= end) {
                if(sources[i] <= sources[j]){
                    temp[k++]=sources[i++];
                }else{
                    temp[k++]=sources[j++];
                }
            }
    
            while (i <= mid) {
                temp[k++]=sources[i++];
            }
    
            while (j <= end) {
                temp[k++]=sources[j++];
            }
    
            //将temp赋给sources
            for (i = 0; i < k; i++){
                sources[start + i] = temp[i];
            }
        }
    
        /** * @Comment * @Author Ron * @Date 2017年10月26日 下午4:28:04 * @param sources 待排序的数组 * @param gap 子序列长度 * @return */
        static void mergeGroup(int[] sources,int gap){
            int margedLength = 0;//已归并的序列起始下标
            int length = sources.length;
    
            for(margedLength = 0 ; margedLength + gap*2 - 1 < length; margedLength += gap*2){
                //合并两个子序列
                merge(sources, margedLength, margedLength+gap-1, margedLength+2*gap-1);
            }
    
            if (margedLength + gap - 1 < length) {
                //合并剩下的子序列
                merge(sources, margedLength, margedLength+gap-1, length-1);
            }
        }
    
        /** * @Comment 归并排序（从上到下） * @Author Ron * @Date 2017年10月26日 下午3:42:12 * @return */
        static void mergeSortOne(int[] sources){
            if(sources == null){
                return;
            }
    
            //分组合并
            for(int gap=1; gap < sources.length; gap *= 2){
                mergeGroup(sources,gap);
            }
        }
    
        /** * @Comment 二分归并 * @Author Ron * @Date 2017年10月26日 下午5:58:42 * @param sources 需要排序的序列 * @param start 序列起始位置 * @param end 序列结束位置 * @return */
        static void mergeDivide(int[] sources,int start,int end){
            if(sources==null || start >= end){
                //子区间长度为1，返回
                return;
            }
    
            int mid = (start+end)/2;
    
            mergeDivide(sources,start,mid);
            mergeDivide(sources,mid+1,end);
    
            merge(sources, start, mid, end);
        }
    
        public static void main(String[] args) {
            int[] a = {
       80,30,60,40,20,10,50,70,90};
            mergeSortOne(a);
            for (int i=0; i<a.length; i++){
                System.out.printf("%d ", a[i]);
            }
             System.out.printf("\n");
            int[] a2 = {
       80,30,60,40,20,10,50,70,90};
            mergeDivide(a2,0,a2.length-1);
    
            for (int i=0; i<a2.length; i++){
                System.out.printf("%d ", a2[i]);
            }
        }
    }

[SouthEast]: /images/20220606/5900e371742a4bcabcd0166a479c48ac.png
[SouthEast 1]: /images/20220606/32cffc63b10f41029e647bf936b00d59.png
[SouthEast 2]: /images/20220606/17cbb1c170a14ce5bc3d5342daf11fad.png