快速排序也是属于十大经典排序算法之一。号称是所有排序算法中性能最好的排序算法。但事无绝对，极端情况下 快速排序也会退化，退化后的性能为O(n^2)。
什么叫快速排序？
老规矩，给快速排序下一个定义，什么叫快速排序？这里借用一下百度百科的解释：
快速排序（Quicksort）是对冒泡排序算法的一种改进。 [1]
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中 一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可 以递归进行，以此达到整个数据变成有序序列
用人话翻译一下就是：
1. 选择一个基准值，
2. 比基准小数的放一边，比基准大的数放另外一边。
3. 对基准值左边和右边数的集合继续进行上面的第一步和第二步操作，直到整个数据集合变有序。
实现
上面的人话翻译就是快速排序算法的实现步骤，依据此步骤我们来尝试实现快速排序。 先随便创建一个随机数组。 84, 51, 53, 8, 62, 96, 64, 99, 94, 17 。
第一步，选取0号位数为基准值。如下图所示。
选取基准值这一步方法蛮多，可以选第一个数也可以选最后一个，也可以 选中间位置数。只是具体的实现上会有所差异。
图1
第二步，将小于基准值的数排在基准值的左边，大于基准值的数排在基准值得右边。
第二步的具体实现这里采用双指针法，具体实现上和大部分人写的有点出入，如果大家发现有不正确的地方请 告知。具体操作方法分为以下几个小步骤：
1. 左指针i位置为base位置加1，即上图的1号位。右指针j指向数组的末尾，即上图的9号位。
2. 左指针i向右移动，直到找到大于base值得数时停下（这里需要注意边界条件。 i不能超出右边9号位。即需要 满足i<=end的前提下进行左移）。
3. 右指针j向左移动，直到找到小于base值得数时停下（同步骤2这里也需要注意边界， j的值不能超出左边界， 即需要满足j>=0的条件下进行右移）。
图2
4. 如果i<j，交换i和j指向的数字
图3
5. 继续上面的步骤2和步骤3，直到i大于j时结束，跳出循环。如下图所示。
图4
6. 这个观察上图发现，以i和j的中间位置为界限， i位置到9号结束位置的数都大于base基准值。 1号位到j号位的 数均小于base基准值。小数放base左边，大数放右边。如下图图5所示。
图5
这里有个问题，如果按上图这样做分割操作，小于base值得数需要整体左移，性能消耗过大。通过对比图5和图4发现base值的最终位置和上图的j指针指向的位置是同一个位置。所以只需要简单的将j和base进行交换即可。
第6步的最终操作即是交换base和j的值。完成后结果如下：
图6
以上步骤用Java代码来实现，代码为：
public static void quickSort(int[] array, int start, int end) {
int base = array[start]; //选取第一个值为base基准值
int i = start + 1; //左指针指向base+1的位置
int j = end;//右指针j指向数组的末尾
while (i < j) {
while (i <= end && array[i] < base) { //i指针右移动，遇到大于base值的数停止
i++;
}
while (j >= 0 && array[j] > base) { //j指针左移动，遇到小于base值的数停止
j--;
}
if (i < j) { //i小于j，即两个指针未相遇时交换两个指针指向的值
swap(array, i, j); //交换i和j指向的值
}
}
swap(array, start, j); //第二步的第6小步骤，交换基准和j指向的值
}第三步,以基准值为划分，对左右两边的两个集合继续做第一步和第二步的操作。这里采用递归就能简单的实现。
- 对左边小于base的数据集合做快排
quickSort(array, start, j - 1);- 对右边大于base的数据集合做快排
quickSort(array, j + 1, end);递归时需要一个结束条件，当start >= end时数据出错，以此为递归结束条件。完整的代码实现为：
public static void quickSort(int[] array, int start, int end) {
if (start >= end) return; //递归结束条件
int base = array[start]; //选取第一个值为base基准值
int i = start + 1; //左指针指向base+1的位置
int j = end;//右指针j指向数组的末尾
while (i < j) {
while (i <= end && array[i] < base) { //i指针右移动，遇到大于base值的数停止
i++;
}
while (j >= 0 && array[j] > base) { //j指针左移动，遇到小于base值的数停止
j--;
}
if (i < j) { //i小于j，即两个指针未相遇时交换两个指针指向的值
swap(array, i, j); //交换i和j指向的值
}
}
swap(array, start, j); //第二步的第6小步骤，交换基准和j指向的值
quickSort(array, start, j - 1); //对左边小于base的数据集合做快排
quickSort(array, i, end); //对右边大于base值得数据集合做快排
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}算法分析
时间复杂度
最坏情况，如果遇到数组已经是排序ok的或者是逆序（即和我们预期的排序顺序不相符），划为两部分时，一部分 有N-1个元素，另外一部分0个元素。
例如 [8, 17, 51, 53, 62, 64, 84, 84, 94, 96, 99] 数组，我们选取0号位数字8为基准值，划分出来的两个 数据集合就是[] 、 [17, 51, 53, 62, 64, 84, 84, 94, 96, 99]。右边集合继续划分，选17来做基准，即每次选中的都是 集合中的最小值。此时就是快排的最坏情况。时间复杂度为 O(n^2)
最好情况，既然知道最差情况，取反就是最好情况。就是每次划分时恰好取到的基准值就是数组的中间值。以此为 划分依据，两边元素个数相同。时间复杂度为O(nlogn)
平均时间复杂度，O(nlogn)
详细的推导可以参考这里：
https://zhuanlan.zhihu.com/p/61554182
观察以上快排的实现代码发现，快排算法可以理解为是原地排序算法，只利用了额外的一个空间，即为O(1)。此外 还利用了递归堆栈空间。所以总的复杂度为O(1) + O(堆栈)。
按上面时间复杂度的分析，最坏情况下快排会退化，差不多要进行N-1次的递归。所以空间复杂度为O(1) + O(n-1) = O(n)
最好情况下，每次都二分。时间复杂度为O(1) + O(logn) = O(logn) 平均空间复杂度即为O(logn)
稳定性
这里仍然只记录结论，快排排序是不稳定性的排序算法。
Quicksort is not stable, since it exchanges nonadjacent elements.