题目描述

blablabla

样例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        String[] arr = reader.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(arr[i]);
        }
        mergeSort(a, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {//利用arr来保存整个数组
        if (l >= r) {
            return;
        }
        int mid =( l + r) >> 1;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);//递归先帝后归。
        int low = l, hight = mid + 1, k = 0;
        int[] temp = new int[r - l + 1];
        while (low <= mid && hight <= r) {
            if (arr[low] > arr[hight]) {
                temp[k++] = arr[hight++];
            } else {
                temp[k++] = arr[low++];
            }
        }
        while (low <= mid) {
            temp[k++] = arr[low++];}
            while (hight <= r) {
                temp[k++] = arr[hight++];
            }
            for (int i = l, j = 0; i <=r; i++, j++) {
                arr[i] = temp[j];
            }
        }
    }

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla