归并排序

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

注：快排不能保证所有数据组都是O(nlogn)，但是平均是O(nlogn)。堆排序会用到堆，不好实现。

写的不错的文章：归并排序

改进的模板(在刷题中给定的数据序列多为不定长的，所以我用Arraylist)

package Template;

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author knight1527
 * Created with IntelliJ IDEA.
 * User: suse_QiHang
 * Date: 2021/06/30 15:07
 * Description:
 * Version: V1.0
 */
public class 归并排序 {
    public static ArrayList<Integer> list=new ArrayList<>();

    public static void sort(ArrayList<Integer> list){
        int[] temp=new int[list.size()];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        devide(list,0,list.size()-1,temp);
    }

    private static void devide(ArrayList<Integer> list,int left,int right,int[] temp){
        if(left<right){
            int mid=(right+left)/2;
            devide(list,left,mid,temp);//左边归并排序，使得左子序列有序
            devide(list,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(list,left,right,mid,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(ArrayList<Integer> list,int left,int right,int mid,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while(i<=mid && j<=right){
            if(list.get(i)<=list.get(j)){
                temp[t++]=list.get(i++);
            }else{
                temp[t++]=list.get(j++);
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++]=list.get(i++);
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++]=list.get(j++);
        }
        t=0;
        //将temp中的元素全部拷贝到原数组中
        while(left<=right){
            list.set(left++,temp[t++]);
        }
    }
    public static void main(String[] args) throws IOException {

        /*
         *单组输入，以回车符结束输入。
         */
        /* Scanner scan = new Scanner(System.in);
        String l = scan.nextLine().trim();//去除前导空格，防止扫描错误
        Scanner scan_l = new Scanner(l);
        while(scan_l.hasNextLine()) {
            list.add(scan_l.nextInt());
        }
        sort(list);
        System.out.println(list.toString());*/

        /*
         *多组输入
         */
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        while(sc.hasNextLine()){
            //\\s+可以处理多个空格
            String[] s=sc.nextLine().trim().split("\\s+");
            for(String str:s){
                list.add(Integer.parseInt(str));
            }
            sort(list);
            System.out.println(list.toString());
            list.clear();
        }
    }
}