归并排序

归并排序，时间复杂度是 O(nlogn)

【输入描述】

输入两行。第一行输入数组大小 n 。第二行输入 n 个数字。

【输出描述】

输出一行。输出排序后的数字。

【输入样例】

8
7 13 4 5 8 1 11 9
【输出样例】

1 4 5 7 8 9 11 13
【参考程序】

//小牛编程
#include <iostream>
using namespace std;

const int MAXN = 10001;
int arr[MAXN];

// 将数组arr[]中的元素合并到temp[]中
void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left;    //左序列游标(下标)
    int j = mid + 1; //右序列游标
    int t = 0;       //临时数组游标

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) { //降序改成 >
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }

    //将左序列剩余元素放进temp中
    while (i <= mid) {
        temp[t++] = arr[i++];
    }

    //将右序列剩余元素放进temp中
    while (j <= right) {
        temp[t++] = arr[j++];
    }

    //将temp中所有元素全部拷贝到arr中
    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

//归并排序（升序），temp临时数组，避免递归中频繁开辟空间
void mergeSort(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        //分左边子序列，左边归并排序
        mergeSort(arr, left, mid, temp);

        //分右边子序列，右边归并排序
        mergeSort(arr, mid + 1, right, temp);

        //合并子序列
        merge(arr, left, mid, right, temp);
    }
}

int main() {
    int n;
    cin >> n;

    // 输入n个数字
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 临时数组
    int temp[MAXN];

    // 归并排序（升序）
    mergeSort(arr, 0, n - 1, temp);

    //排序结果
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

经典算法

归并排序