题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N = 100010;
int tmp[N],a[N];
void merge_sort(int a[],int l,int r)
{
    if (l >= r)return;//区间中元素个数为1或0
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int i = l, j = mid + 1,k = 0;//i为指向左半边的起点，j为指向右半边的起点
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid)//左半边未循环完
    {
        tmp[k++] = a[i++];
    }
    while (j <= r)
    {
        tmp[k++] = a[j++];
    }
    for (int k = 0,i = l;i <= r; k++, i++)
    {
        a[i] = tmp[k];
    }
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++)cout << a[i] << " ";
}