排序算法之归并排序

归并排序算法是排序算法中的经典算法之一，其核心思想是利用归并的思想实现的排序方法，该算法采用经典的分治策略，将排序问题分解成一些小问题后递归求解。下面先通过一些图来帮助理解归并排序的思想。

分解待排序序列

1024555-20161218163120151-452283750.png

上图显示了归并排序分解待排序序列的步骤，首先将待排序序列分成两个子序列，然后将两个子序列再分别分成子序列，依次进行下去，直至子序列的长度为1不能再分为止。

合并相邻有序子序列

将已经有序的子序列合并成一个有序序列，以上图为例，下图展示了合并的过程。

1024555-20161218194508761-468169540.png

下面通过代码来实现归并排序算法

import java.util.Arrays;
import java.util.Scanner;
public class MergeSort {
     public static void main(String[] args){
           System.out.print("输入：\n");
           Scanner scan = new Scanner(System.in);
           int i=0;
           int n =scan.nextInt(); //输入的待排序序列长度
           int [] arr=new int[n];
           for(i=0;i<n;i++){
                arr[i]=scan.nextInt();
           }
           int[] temp=new int[arr.length]; 
           sort(arr,0,arr.length-1,temp);
           System.out.println(Arrays.toString(arr));            
    }
 
     public static void sort(int[] arr, int left, int right, int[] temp){
            if(left<right){
                int mid = (left+right)/2;
                sort(arr,left,mid,temp); //将左子序列排序
                sort(arr,mid+1,right,temp);//将右子序列排序
                merge(arr,left,mid,right,temp);//将两个子序列合并 
           }
     }

   public static void merge(int[] arr, int left, int mid, int right, int[] temp){
         int t = 0;
         int i = left;
         int j =mid+1;
         while(i<=mid&&j<=right){
               if(arr[i]<=arr[j]){
                  temp[t++]=arr[i++];
               }else{
                  temp[t++]=arr[j++];
              }
        }
       while(i<=mid){
             temp[t++]=arr[i++];
       }
      while(j<=right){
            temp[t++]=arr[j++];
      }
     t=0;
     while (left<=right){
           arr[left++]=arr[t++];
    }        
}
}

从上面可以看出，归并排序的效率是比较高的，设数列长度为N,将数列长度分割成小数列需要logN步, 每一步都是合并有序数列的过程，所以合并的时间复杂度为O(N)，故归并排序算法的总时间复杂度为NlogN。