P1177 【模板】排序题解

sort 函数：

CPP

#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

级别的复杂度，所以排序前需要先随机打乱。

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

代码：

CPP

#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;
}

P1177 【模板】排序题解

文章操作

相关推荐

评论

P1177 【模板】排序题解