背模板

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], t[N];
void swap_m(int q[], int l, int r)
{
    if(l >= r)  return;
    int mid = l + r >> 1;
    swap_m(q, l , mid);
    swap_m(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j])   t[k++] = q[i++];
        else    t[k++] = q[j++];
    while(i <= mid) t[k++] = q[i++];
    while(j <= r)   t[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> q[i];
    swap_m(q, 0, n - 1);
    for(int i = 0; i < n; i++)  cout << q[i] << " ";
}

Java 代码

import java.util.Scanner;
public class Main
{
    static int N = 1000010;
    static int q[] = new int [N];
    public static void main(String[] args)
    {
        Scanner get = new Scanner(System.in);
        int n = get.nextInt();
        for(int i = 0; i < n; i++)  q[i] = get.nextInt();
        swap_m(q, 0, n - 1);
        for(int i = 0; i < n; i++)  System.out.print(q[i] + " ");
    }
    public static void swap_m(int q[], int l, int r)
    {
        if( l >= r) return;
        int mid = l + r >> 1;
        swap_m(q, l, mid);
        swap_m(q, mid + 1, r);
        int t[] = new int [r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
            if(q[i] <= q[j]) t[k++] = q[i++];
            else    t[k++] = q[j++];
        while(i <= mid) t[k++] = q[i++];
        while(j <= r)   t[k++] = q[j++];
        for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
    }
}