内部排序之归并排序（MergingSort）

浅浅的花香味﹌ 2021-09-11 04:00 308阅读 0赞

## **一、基本思想** ##

> 将两个已经排序好的有序列表合并成一个新的有序表。根据分治策略，我们会发现从上往下，就是将一个乱序表一直递归划分，划分到最后就只剩一个元素，显然有序。

## **二、示意图** ##

![这里写图片描述][20160927110723651]  
从底下往上看，整个算法就像分治策略中的最大子数组问题。  
[最大子数组问题][Link 1]

## **三、算法** ##

整个算法分为两个部分，一个是对两个有序子表的合并；一个是对乱序表的划分。  
*合并：*  
这部分很简单，就是逐个读取连个子表的最小值。  
![这里写图片描述][20160927111124731]  
*划分：*  
![这里写图片描述][20160927111258703]

public class Main{
        public static void main(String[] args){
            int[] a = new int[]{3,1,5,3,8,-1};
            mergeSort(a, 0, a.length-1);
            for(int n : a){
                System.out.println(n);
            }
        }
    
        public static void mergeSort(int[] a, int left, int right){
            if(left<right){
                int mid = left + (right-left)/2;
                mergeSort(a, left, mid);
                mergeSort(a, mid+1, right);
                merge(a, left, mid, right);
            }
        }
    
        public static void merge(int[] a, int left, int mid, int right){
            int first = left, second = mid+1, k=0;
            int[] temp = new int[right-left+1];
            while(first<=mid && second<=right){
                if(a[first]<=a[second]){
                    temp[k++] = a[first++];
                }else{
                    temp[k++] = a[second++];
                }
            }
            while(first<=mid) temp[k++] = a[first++];
            while(second<=right) temp[k++] = a[second++];
    
            k = 0;
            for(int i = left; i<=right; i++){
                a[i] = temp[k++];
            }
        }
    }

import org.junit.Test;
    public class MergeSort {
        //两路归并算法，两个排好序的子序列合并为一个子序列
        public void merge(int []a,int left,int mid,int right){
            int []tmp=new int[a.length];//辅助数组
            int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
    
            while(p1<=mid && p2<=right){
                if(a[p1]<=a[p2])
                    tmp[k++]=a[p1++];
                else
                    tmp[k++]=a[p2++];
            }
    
            while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
            while(p2<=right) tmp[k++]=a[p2++];//同上
    
            //复制回原素组
            for (int i = left; i <=right; i++) 
                a[i]=tmp[i];
        }
    
        public void mergeSort(int [] a,int start,int end){
            if(start<end){//当子序列中只有一个元素时结束递归
                int mid=(start+end)/2;//划分子序列
                mergeSort(a, start, mid);//对左侧子序列进行递归排序
                mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
                merge(a, start, mid, end);//合并
            }
        }
    
        @Test
        public void test(){
            int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
            mergeSort(a, 0, a.length-1);
            System.out.println("排好序的数组：");
            for (int e : a)
                System.out.print(e+" ");
        }
    }

[剑指offer：合并两个排序的链表][offer]

[20160927110723651]: /images/20210520/7adb8858389a4d468b892d55e844e7ed.png
[Link 1]: http://blog.csdn.net/qq_16234613/article/details/52669732
[20160927111124731]: /images/20210520/a06abec4266a4644972ca041dd28f683.png
[20160927111258703]: /images/20210520/6a8d2dd338f54ecc9c0484e77bb9fd66.png
[offer]: https://blog.csdn.net/qq_16234613/article/details/83108101