C++

$\color{#cc33ff}{— > 算法基础课题解}$

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

归并排序

$模板题$

$归并排序：$

$1、[L, R] => [L, mid], [mid + 1, r]$
$2、递归排序[L, mid]和 [mid + 1, r]$
$3、归并，将左右两个有序序列合并成一个有序序列$

时间复杂度： $O(nlog_2n)$

$code1:$

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n, q[N], tmp[N];

void merge_sort (int q[], int l, int r){

    //分治 思想

    if (l >= r) return ; // 如果区间里面元素个数是1个或者没有的话，返回

    //确定分界点
    int mid = l + r >> 1; // 位运算 相当于 （l + r）/ 2 

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 排 左边和右边

    //归并
    int k = 0, i = l, j = mid + 1; // i 指向左边的起点 j 指向右边的起点

    while (i <= mid && j <= r){ // i 小于左边的边界  j 小于右边的边界
        if (q[i] < q[j]) tmp[k ++] = q[i ++]; // 将左右两边小的那一个数存入辅助数组tmp中
        else tmp[k ++] = q[j ++];
    }
    while (i <= mid) tmp[k ++] = q[i ++]; // 如果左边没有循环完，把左边剩余的数存入 tmp数组
    while (j <= r) tmp[k ++] = q[j ++]; // 如果左边没有循环完，把左边剩余的数存入 tmp数组

    // 最后把排好序的数放回 原数组 q 中
    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

int main(){

    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);

    merge_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

$code2:$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];

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 k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] < q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }

    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];

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

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> q[i];

    merge_sort(0, n - 1);

    for (int i = 0; i < n; i ++) cout << q[i] << ' ';

    return 0;
}