快速排序

相关

D0001 D0002 D0003

首先是原理

快速排序是基于分治思想的一种算法。

大致做法是

1. 确定分界点x，即在所有待排序中的数中选择一个数字为分界点。例如待排序的数组为a[l]-a[r]，l和r是数组的左右边界，x可以取a[l]，a[r]，a[(l+r)/2]，a[随机]（随机数在l-r之间）。
2. 调整区间，所有小于等于x的在左边，所有大于等于x的数在右边。
3. 递归处理左右两段，直至无法处理。

需要注意的是边界问题，如何处理边界的快捷方式是背一个测试没有问题的模板，可以有效减少在比赛时的调试时间。

第二种调整区间的做法有很多，但是要尽量做到不开临时空间，且时间复杂度合理。

较好的办法：可以在数组的两端各放一个指针，向中间运行，当左边的指针大于选定x且右边指针小于x时，交换左右数值。

当两指针相遇的时候即完成第一次处理，接下来递归处理左右两段，反复递归直到最后。

纯递归快排：

代码：

#include<iostream>
using namespace std;
int n;
int q[100010];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int x =q[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> q[i];
	}
	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		cout << q[i] << " ";
	}
	return 0;
}

这样的快速排序有的时候会被卡，主要是因为如果x取数组左端的话，数据为顺序的时候该代码会劣化为 O(n²) （？大概是这么算的吧，有错误的话请指正），相当于冒泡排序，时间复杂度会大大增加。可以考虑使用随机取值以及左中右三者取中间值的办法。

稍加一点点优化的快排：

代码：

#include<iostream>
#include<ctime>
using namespace std;
int n;
int q[100010];
void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;
	if (r - l < 10)    //这里是为了减少递归次数，最后的几次相对于递归，插入排序的消耗会更少（但是测出来没多少差距，可能是数据量依然不够）。
	{
		int i, j;
		int temp;
		for (i = l + 1; i < r + 1; i++)
		{
			temp = q[i];
			for (j = i; j > l&& q[(j - 1)] > temp; j--)
			{
				q[j] = q[j - 1];
			}

			q[j] = temp;
		}
		return;
	}
	srand((unsigned)time(NULL));
	int pivotPos = rand() % (r - l) + l;
	int x = q[pivotPos], i = l - 1, j = r + 1;//使用随机数取x避免时间复杂度劣化。

	//	int x = q[l]>=q[(l+r)/2]?(q[(l+r)/2]>=q[r-1]?q[(l+r)/2]:(q[l]>=q[r-1]?q[r-1]:q[l])):(q[l]>=q[r-1]?q[l]:(q[(l+r)/2]>=q[r-1]?q[r-1]:q[(l+r)/2])), i = l - 1, j = r + 1;
        //注释的这一段是使用了问号表达式取q[l]，q[(l+r)/2]，q[r-1]中的中位数，同样是可以一定程度上的避免时间复杂度劣化。
        //不要学习这种问号表达式的方法，只是突发奇想，使用if判断，会使代码更加简单明了。（避免被队友打死）
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}
int main()
{
	std::ios::sync_with_stdio(false);//关闭输入流同步提高读入速度（貌似c++17上提升的不多，但是对于较老版本提升很大。同样，如果仍然超时可以尝试使用快读。
	cin >> n;    //排序n个数
	for (int i = 0; i < n; i++)
	{
		cin >> q[i];
	}
	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		cout << q[i] << " ";
	}

	return 0;
}

上面的模板中加入了少量的优化，可以在超时卡在刚好差一点点的时候使用。更加深入的优化等之后更新。

没了