题解 | #排序#

#include <iostream>
using namespace std;
const int N = 101;
int temp[N];//归并排序时的临时数组

void quick_sort(int q[], int l, int r){//快速排序
    if (l >= r) return ;
    int i = l - 1, j = r + 1, mid = q[l + r >> 1];
    while (i < j) {
        do i ++; while (q[i] < mid);
        do j --; while (q[j] > mid);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

void merge_sort(int q[], int l, int r){//归并排序
    if(l >= r) return ;

    //分治排序
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    //合并
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if(q[i] < q[j]) temp[k ++] = q[i ++];
        else temp[k ++] = q[j ++];
    }
    while(i <= mid) temp[k ++] = q[i ++];
    while(j <= r) temp[k ++] = q[j ++];

    for(int i = l, k = 0; i <= r; i ++) q[i] = temp[k ++];
}

int main() {

    int n;
    while(cin >> n){
        int q[N];
        for (int i = 0; i < n; i ++) {
            cin >> q[i];
        }
        //quick_sort(q, 0, n - 1);
        merge_sort(q, 0, n - 1);
        for (int i = 0; i < n; i ++) {
            cout << q[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")