首先，假设有一个原始杂乱的数列，权值为 : 3、1、3、6、4、0  。

首先在这个有6个值的数列，先选取一个基准数，这个基准数选法不唯一。

（我们这里的基准数选择数列的第一个就好，其他原理也相同，算法程序略不同）。

  1. 初始基准数: 3。
  2. L和R表示当前数列的第一个元素的位置，最后一个元素的位置。
  3. 图中有两个指针分别写着左和右，初始时指向数列的 L-1 和 R+1的位置。

快排的基本做法:

第一趟-移动左指针:

移动左指针，当遇到第一个不小于基准数的数，那么停止。到3成立，所以停止。

 

第一趟-移动右指针:

移动右指针，当遇到第一个不大于基准数的数，那么停止。这里，到0这已经成立。

 

第一趟交换:交换

然后此时:如果左指针在右指针的左边，那么交换 3 和 0。如果不在，会有另外的选择。

 

第二趟-移动左右指针:

和第一趟是同理的,移动完毕后的结果如图。

第二趟-是否交换？

此时发现右指针在左指针左侧了，不符合了左指针在右指针的左边的条件，所以不交换。

此时的操作:把这个大数列分成两个小数列，从L到右指针所有的数作为一个新数列A，从左指针到R的数作为一个新的数列B。

新的数列A:

新数列B：

分治:A和B遵从同样的规则。

注意！此时的基准数，是A和B各自的基准数了，新的基准数。A的基准数:0  B的基准数:6。

 

以数组A为例A，流程:

移动指针,分别到数值为0的位置----》并且此时符合交换条件，左指针在左，那么交换0、0，所以没什么大变化。

继续移动指针。右指针跑到了更左边的位置。我们需要对A继续分治。

 

根据指针位置，分出新的分组:A1、A2

 

此时A1就剩一个元素了，那么我们就不管他了

A2还需要最后的移动,A2的基准值:1

左指针在更左边，进行交换。得到最后的A2数列: 0 、1

A = A1 + A2 = { 0、0、1}

B = {3、4、6}

总数列 = A + B = {0、0、1、3、4、6}

 

总结:快排几个重要的点

  1. 基准值的选取
  2. 移动指针
  3. 是否交换？
  4. 分治

下面给出快排模板:

#include<iostream> 

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

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()
{
	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]);
}