P1177 【模板】排序 题解

· · 题解

P1177 【模板】排序

sort 函数：

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

using namespace std;

const int N = 1e5 + 5;

int n, a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++ ) printf("%d ", a[i]);
    return 0;
}

手写快排：理论就是每次选取一个基准值放在中间，用两两交换的方式将所有小于它的数放在左边，大于它的数放在右边。因为基准值一般是选取第一个所以如果数组本身有序就会被卡到 n^2 级别的复杂度，所以排序前需要先随机打乱。

不过还是不能通过这道题，因为本题的最后一个数据的点全部都是一样的数。所以我增加了一个判断，每次递归子区间时，都先判断一下是否有序，无序时再进行递归，这样就可以通过。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, a[N];

bool check(int l, int r)
{
    for (int i = l; i < r; i ++ ) if (a[i] > a[i + 1]) return 0;
    return 1;
}

void sort(int l, int r)
{
    if (l >= r) return;
    int k = a[l], p = l + 1, q = r;
    while (p <= q)
    {
        while (p <= q && a[p] <= k) p ++ ;
        while (p <= q && a[q] >= k) q -- ;
        if (p < q) swap(a[p], a[q]);
    }
    swap(a[l], a[q]);
    if (!check(l, q - 1)) sort(l, q - 1);
    if (!check(q + 1, r)) sort(q + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    random_shuffle(a + 1, a + n + 1);
    sort(1, n);
    for (int i = 1; i <= n; i ++ ) printf("%d ", a[i]);
    return 0;
}