目录

一、快排思想和时空复杂度

二、举例

三、代码 

一、快排思想和时空复杂度

快速排序是一种交换排序，采用了分治的策略。

基本思想是：

1.先从数列中，取一个数作为基准数pivot，通常我们取区间的第一个元素；

2.创建两个指针，left指针指向待排序列的第一个元素，right指针指向待排序列的最后一个元素。

3.从right指针开始，找到第一个比pivot小的元素，然后让left指针指向的元素等于right指针此时指向的元素；

因为left首次指向的元素是pivot，所以被覆盖了没有关系。

4.然后再从left开始，找到第一个比pivot大的元素，让right指向的元素等于left指向的元素。

因为right指向的元素已经复制了一份到了pivot的前面，所以被覆盖了也没有关系。

5.重复上述操作，直到left=right。

此时将pivot元素放在left和right同时指向的位置即可。

6.这一趟排序将整个待排序列分为了三个子序列：

第一个：[0，pivot-1]

第二个：[pivot]

第三个：[pivot+1,length]

然后，我们再递归地对第一个和第三个子序列进行快速排序即可。

当然我们需要一个递归出口，就是如果left一开始就大于等于了right，那么说明此时区间只有一个元素。

时间复杂度分析：

由于每一次排序我们都需要进行O(N)级别的交换，

而每一次排序都需要将表划分为两个子表，再进行递归

所以递归次数平均下来是O(LOG2N)级别的。

综上，快排的时间复杂度是O(NLOG2N)。

但是，如果刚开始的排序表是逆序的或者基本有序的，就会退化成冒泡排序。

此时的时间复杂度为O(N^2)。

空间复杂度分析： 

由于快排是递归的，需要借助一个递归工作栈，其容量与递归调用的最大深度一致。

最好情况下和平均情况下是O(LOG2N),因为基于二分法；最坏情况是O(N)，因为需要进行n-1次递归调用。

二、举例

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0;  j = 9;   X = a[i] = 72

由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为：

i = 3;   j = 7;   X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。   

三、代码 

void quickSort(vector<int>& v,int L,int R)
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int pivot = v[left];
	while (left < right)
	{
		//找到右指针指向的第一个比pivot小的元素
		while (left < right && v[right] >= pivot)
		{
			right--;
		}
		if (left < right)
		{
			v[left] = v[right];
		}
		while (left < right && v[left]<=pivot)
		{
			left++;
		}
		if (left < right)
		{
			v[right] = v[left];
		}
		if (left >= right)
		{
			v[left] = pivot;
		}
	}
	quickSort(v, L, right - 1);
	quickSort(v, right + 1, R);
}