AcWing 787. 归并排序

一、 题目描述

给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式

输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式

输出共一行，包含 n 个整数，表示排好序的数列。
数据范围

1≤n≤100000
输入样例

1. 5
2. 3 1 2 4 5

复制代码

输出样例

1. 1 2 3 4 5

复制代码

二、思路分析 （分治思想)

归并排序是一种采用分治策略的排序算法。其基本思想是：将一个数组分成两半，对这两部分分别进行排序，然后将排序后的两部分合并起来。具体步骤如下：

• 分割： 将数组从中间分成两部分，分别进行递归排序。
  
• 合并： 当两个子数组已经排好序时，通过合并操作将它们合并成一个有序数组。
  关键步骤：
  
• 分割： 将数组分成两半，可以通过递归方式不断拆分直到每个子数组只有一个元素。
  
• 合并： 对两个有序的子数组进行合并，生成一个有序数组。
  

归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)，其稳定性较好。
三、代码实现

[code]import java.util.Scanner;public class Main {    static int N = 100010;    static int[] a = new int[N];    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        for (int i = 0; i < n; i++) {            a = scanner.nextInt();        }        merge_sort(0, n - 1);        for (int i = 0; i < n; i++) {            System.out.println(a);        }    }    private static void merge_sort(int l, int r) {        if (l >= r) return;        int mid = l + r >> 1;        merge_sort(l, mid);        merge_sort(mid + 1, r);        int[] t = new int[N];        int i = l, j = mid + 1, k = 0;        while (i