快速排序是由东尼霍尔所发展的一种排序算法。在平均n个项目要Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
算法步骤：
从数列中挑出一个元素，称为 “基准”（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
具体实现有两种方法：
挖坑法指针交换法
挖坑法
给定一组原始数列，要求从小到大排序：
首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：
接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。
在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来所在的位置成为了新的坑。同时，left向右移动一位。
此时，left左边绿色的区域代表着小于基准元素的区域。
接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。
在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。
此时，right右边橙色的区域代表着大于基准元素的区域。
下面按照刚才的思路继续排序：
8>4，元素位置不变，right左移
2<4，用2来填坑，left右移，切换到left。
6>4，用6来填坑，right左移，切换到right。
3<4，用3来填坑，left右移，切换到left。
5>4，用5来填坑，right右移。这时候left和right重合在了同一位置。
这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。
指针交换法：
给定原始数列如下，要求从小到大排序：
开局和挖坑法相似，我们首先选定基准元素Pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素：
接下来是第一次循环，从right指针开始，把指针所指向的元素和基准元素做比较。如果大于等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。
在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。
轮到left指针行动，把指针所指向的元素和基准元素做比较。如果小于等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动。
由于left一开始指向的是基准元素，判断肯定相等，所以left右移一位。
由于7 > 4，left指针在元素7的位置停下。这时候，我们让left和right指向的元素进行交换。
接下来，我们进入第二次循环，重新切换到right向左移动。right先移动到8，8>2，继续左移。由于2<8，停止在2的位置。
切换到left，6>4，停止在6的位置。
元素6和2交换。
进入第三次循环，right移动到元素3停止，left移动到元素5停止。
元素5和3交换。
进入第四次循环，right移动到元素3停止，这时候请注意，left和right指针已经重合在了一起。
当left和right指针重合之时，我们让pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。
代码实现：
如果觉得《实现快速排序的算法_排序算法-快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
