目录
一、快排思想和时空复杂度
快速排序是一种交换排序，采用了分治的策略。
基本思想是：
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);
}