归并排序 java版本

blablabla

样例

import java.io.*;
class Main{
    private static int[] temp;
    public static void merge_sort(int[] m, int l, int r){
        if(l>=r) return ;
        int mid = (l+r)>>1;
        merge_sort(m,l,mid);
        merge_sort(m,mid+1,r); //归并 直到 左右俩边各一个元素
        int k = 0,i = l,j = mid + 1; // i 指向左半边起点 j 是指向右半边起点
        while(i<=mid&&j<=r){         //归并，比较大小，按序添加到temp数组
            if(m[i]>m[j]) temp[k++] = m[j++]; 
            else if(m[i]<=m[j]) temp[k++] = m[i++]; //这里<=可以保证稳定性
        }
        while(i<=mid) temp[k++] = m[i++]; //如果左半边或者右半边未排完
        while(j<=r) temp[k++] = m[j++];
        for( i = l,j = 0; i <= r ; i++,j++){ //将临时数组赋值给元素组
            m[i] = temp[j];
        }
    }

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] m = new int[n];
        temp = new int[n];
        String[] s = br.readLine().split(" ");
        for(int i = 0; i < s.length; i++){
            m[i] = Integer.parseInt(s[i]);
        }
        merge_sort(m,0,n-1);
        for(int x : m){
            System.out.print(x + " ");
        }
    }
};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla