思路：

1.找一个支点元素pivot，一般选这组数的第一个

2.把大于pivot的数都放在它的右边，小于它的数都放在左边

3.分别对左右子序列进行1、2步操作（分治策略的体现）

示例：

19    97    09    17    01    08

Pivot

↑                                        ↑   

L                                       R

选择第一个元素(19)作为支点pivot，L和R是两个指针，相向移动(R先移动），R要找的是小于pivot的元素，L要找的是大于pivot的元素（因为他们不属于这里），然后二者交换。

最后LR重合时，pivot更换到这个位置   

19    97    09    17    01    08

Pivot

         ↑                              ↑   

         L                             R

   

这时R找到了比pivot小的元素8，L找到了比pivot大的元素97，swap这两个

19    08    09    17    01    97

Pivot

        ↑                               ↑   

        L                              R

R向左移动，找到比pivot小的01，L向右移动，一直移动没找到比pivot大的，然后就与R重合了

19    08    09    17    01    97

Pivot

                                ↑↑   

                               LR

然后把重合位置的元素与pivot交换

01    08    09    17    19    97

                              Pivot

                                ↑↑   

                                LR

此时19就已经到了他应该在的正确位置了

接下来要做的事情就是对19左右两边的子数组递归进行上述操作

左边的子数组：

老规矩，第一个做pivot

01    08    09    17

Pivot

↑                       ↑

L                      R

01    08    09    17

Pivot

↑↑

L  R

R向左移动，没有找到，一直走，与L在初始位置重合，pivot就在这个地方，不用交换了。

（一定要R先走）

此时pivot：01就在自己合适的位置了，再对他左右子数组递归进行上述操作

因为左边没有东西，那就只对右边的子数组操作

同理，R也在L的初始位置与R重合了

08    09    17

Pivot

↑↑

L  R

以此类推，再处理 09   17

就把 01    08    09    17 排好了

到了第二层的右子数组：就 97 一个数字

不用排了，直接排好

所以最终结果就是：
01    08    09    17    19    97

（第一次排序直接就是这个结果，仅仅是巧合）

对一定要R先走的说明：

    当pivot取最左边的数字，就应该R先走，若pivot取最右边的数字，则L先走。

（无论升序降序都是这样）

代码：

//快速排序
#include <iostream>
using namespace std;
void quicksort(int*arr, int left, int right)
{
	if (left >= right)  //首先判断一下传递进来的left和right合不合理
	{
		return;
	}
	int i = left;
	int j = right;    //把left和right赋值给i，j作为他们的初始状态
	int pivot = arr[left];  //让最左边的元素作为支点pivot
	//不是0开始，要递归调用，比如pivot右边的子数组初始下标就不是0，所以不是arr[0]
	while (i < j)  //i与j碰到时，结束一次排序，所以i<j是循环条件
	{
		while (arr[j] >= pivot && i < j)
		{
			j--;  //j（R)要找的是小于pivot的数，所以当arr[j]>=pivot时，此数不用操作，j向左移动（别忘了i<j的限制条件）
		}
		while (arr[i] <= pivot && i < j)
		{
			i++;  //i（L)要找的是大于pivot的数，所以当arr[i]<=pivot时，此数不用操作，i向右移动（别忘了i<j的限制条件）

		}
		if (i < j)  //执行到这一语句，说明j和i都停下来了，若满足i<j则可以进行交换了
		{
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[left], arr[i]); //支点回归它正确的位置。执行到这句的时候，即已经跳出循环了，即i和j相交了。此时交换pivot和arr[i](或arr[j])(此时是一个数）
	quicksort(arr, left, i - 1);  //递归pivot左边的子数组
	quicksort(arr, i + 1, right);  //递归pivot右边的子数组
}
int main()
{
	int a[8] = { 8,3,4,2,5,7,1,6 };
	quicksort(a, 0, 7);
	for (int k = 0; k < 8; k++)
	{
		cout << a[k] << ' ';
	}
	return 0;
}

输出：1 2 3 4 5 6 7 8 

若要进行从大到小的排序：

只需要对一小部分进行修改

//快速排序降序版本
//思路：与升序不同的是，L找的是小于pivot的数，R找的是大于pivot的数，大于pivot的全在左边，小于的全在右边
#include <iostream>
using namespace std;
void quicksort1(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int i, j;
	i = left;
	j = right;
	int pivot = arr[left];
	while (i < j)
	{
		while (arr[j] <= pivot && i < j)
		{
			j--;
		}
		while (arr[i] >= pivot && i < j)
		{
			i++;
		}
		if (i < j)
		{
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[left], arr[i]);
	quicksort1(arr, left, i - 1);
	quicksort1(arr, i + 1, right);
}
int main()
{
	int a[8] = { 8,3,4,2,5,7,1,6 };
	quicksort1(a, 0, 7);
	for (int k = 0; k < 8; k++)
	{
		cout << a[k] << ' ';
	}
	return 0;
}

输出：8 7 6 5 4 3 2 1

快速排序的时间复杂度：

平均：O(nlogn)

最快：O(nlogn)

最慢：