题目描述

归并排序

时间复杂度

nlogn

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    public static int[] q, temp;

    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(in.readLine());
        //归并需要开一个额外的数组, 利用双指针比较左右两边大小.
        //较小的则先入 临时数组. 排完后再放回原数组. 
        //归并先迭代, 迭代到最后一层则是两个相邻的数字比较. 再是相邻的数组比较. 
        temp = new int[n];
        q = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        //这里只把临时数组和原数组都设为全局变量. 
        //好对应快排, 而且不用老是传不变的参数. 没卵用.
        mergeSort(0, n-1);

        for(int i : q){
            System.out.print(i+ " ");
        }

    }

    //a. 先迭代到到最小单位[一个数字]-->再是相邻数组.每次数组长度 * 2.
    //b. 再利用双指针 左右比较.较小的先入临时数组. 全部放完再还原给原数组.
    public static void mergeSort(int l,int r){
        //a1.迭代结束条件
        if(l>=r) return;

        //a2.初始化中值指针
        int mid = l+r>>1;

        //a3.递归， 利用中值分边界
        mergeSort(l, mid);
        mergeSort(mid+1, r);

        //b1.初始化左右指针, 都是从数组头开始,
        //而快排从左右两个端点开始.
        int i = l, j = mid + 1, k = 0;

        //b2.左右数组值比较, 较小的入临时数组.
        while(i<= mid && j<=r){
            if(q[i]<q[j]){
                temp[k++] = q[i++];
            }else{
                temp[k++] = q[j++];
            }
        }
        //b3.插入还有未加入临时数组的数
        while(i<=mid)temp[k++] = q[i++];
        while(j<=r)temp[k++] = q[j++];

        //b4.将 临时数组中排好序的数组重新放入原数组.
        for(i =l, k=0; i<=r; i++,k++){
            q[i] = temp[k];
        }
    }

}