快速排序算法

1. 快排

确定一组数据，即q数组

左端点为了，右端点为r

（1）确定分界点

q[l] 或 q[ (l + r) / 2] 或 q[r] 或任意一个数作为分界点，分界点数为x

（2）调整区间（重点）

使 <= x的数放在左半边，使 >= x 的数放在右半边，两边的数可以乱序，暂时不用排序

（3）利用递归处理左右两端，进行排序

暴力法

（1）开两个额外数组a，b

（2）扫描 l 到 r 的所有数，将 <= x 的值放到a中，将 >= x的数放到b中

（3）将a，b排序后放到q数组中 a[ ] -> q[ ], b[ ]->q[ ];

（4）弊端：额外开辟空间，占用内存

简便方法（指针）

用两个指针i，j指向左端与右端的数

（1）判断指针i所指向的数是否小于x，符合条件时往右移一位，当大于等于x时指针i停下

（2）判断指针j所指向的数是否大于x，符合条件时往左移一位，当小于等于x时指针停下

（3）将i与j指针所指向的数交换，并再次重复1，2，3，直到i，j走到中间位置

（4）两边排序

模板

#include <iostream> // scanf和printf也在iostream里面 ，但cstdio更快一些
#include <cstdio> 
#include <algorithm> //使用swap函数
using namespace std;
const int N = 1000001;

int n;
int q[N];

void quick_sort(int q[ ], int l, int r)
{
	if (l >= r) return ; // 返回一个随机值，该return只是起到一个中止的作用，无需返回特定值

	int x = q[l], i = l - 1, j = r + 1,;
    //x = q[(l+r+1 )/2	一定不能取到边界上，上面的x只是举例
    // x = q[l + 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]);
	}

	if(l < j )quick_sort(q, l, j);//左半部分
	if(i < r)quick_sort(q, j + 1, r);//右半部分

}
int main()
{
	scanf("%d", &n);
	for (int i = 0;i < n;++i) scanf("%d", &q[i]);

	quick_sort(q, 0, n-1);

	for (int i = 0;i < n;++i) printf("%d ", q[i]);

	return 0;
}