P1177

An_Aholic · 2023-05-16 22:42:33 · 个人记录

P1177

快排

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) 
        cout << a[i];
    return 0;
}

↑ lz 在没有括号配对的情况下胡乱造出的没交过的 野生 代码一份，可能会挂。 (雾

回归正题（我肯定不是为了讲这么简单的东东），要写，也得写手写！

（去偷一幅图）

二分！递归！

啊

思路

整体思路：分治， 每一次递归，给一个 mid, 进行某操作，使得左区间 < mid < 右区间。然后，mid 位置就固定了， 就在递归左区间，递归右区间。

首先，我们找到一个中间数（mid， 有些是二分，有些是随机选择一个数（详见 OI -Wiki ））, 然后双指针，初始时分别指向 l 和 r （这次递归的范围）， 然后我们这个双指针，为了满足条件，我们一定是要把左边不符合 < mid 的，和右边不符合 > mid 的交换，最后一定就能保证左区间 < mid < 右区间。

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005];

void Qsort(int l, int r) {
    int mid = a[(l + r) >> 1];
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < mid) {  // 找那个左区间不符合 < mid 的 
            i++;
        }
        while (a[j] > mid) { // 找那个左区间不符合 < mid 的 
            j--;
        }
        //   到此，i, j 分别指向了左，右区间分别不符合条件的 
        if (i <= j) {
            swap(a[i], a[j]);  // 交换 
            i++, j--;
        }
    }
    // j 停留在了左极端的部分 
    // i 停留在了右极端的部分 
    if (j > l)  // 如果这部分区间存在 
        Qsort(l, j); // 接着递归 
    if (i < r) // 基本同上 
        Qsort(i, r);

}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    Qsort(1, n);
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";

}