之所以叫快速排序，是因为快排在实际应用中是表现最好的排序算法。
快速排序采用分治策略对数据进行排序，什么是分治策略呢？简单地说就是“分而治之，各个击破”。啥意思呢？且听我慢慢道来：
假设现在给你一个数组int[] arr = {6, 2, 4, 9, 3, 10}，选择一个基准数（这个可以随便选，为了方便一般选择第一个元素为基准数）pivot = arr[0] = 6;将大于基准数pivot的元素放在pivot右侧，小于pivot的元素放在pivot左侧；这样基准值就处在它应该处在的位置了；然后对基准值左右两侧的子数组再选取基准值进行一轮如上的操作，这样不断的将数组一份为二，每一次都“安顿”好一个数值（基准值），最后一定能够将整个数组排序（“安顿”）好。
现在把上面的叙述抽象成步骤：
- 从数组中挑选一个基准值，并设置i = 0， j = a.length - 1;
- 先从右往左寻找比基准值小的值，再从左往右寻找比基准值大的值，交换它们；重复此步骤，直到 i 和 j 相遇
- 将基准值和a[i]交换以完成归位
- 递归地把"基准值前面的子数组"和"基准值后面的子数组"进行步骤1，2，3
针对上面的步骤有几点说明：
- 基准值一般选择当前数组的第一个元素，这样做是为了代码实现方便，更好理解
- 对于和基准值相等的数值放在左边或右边都可以，同时这也是快速排序不稳定的原因
- 经过步骤2后我们就把基准值“安顿”好了
- 步骤3所谓递归，其实就是不断地把基准值“安顿”好
说的再好都不如图来的畅快：
其实，快速排序算法分为两个部分：分段(Partition)和递归(Recursive)。代码实现如下：
C++代码实现
#include <iostream>
using namespace std;
void swap(int arr[], int i, int j)
{
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
void QuickSortRec(int arr[], int i, int j)
{
if(i > j)
return;
// 以最左侧元素作为pivot基准元素
int left = i;
int right = j;
int pivot = arr[left];
while(left < right)
{
// 从right开始往左寻找 < pivot元素
while(right > left)
{
if(arr[right] < pivot)
{
break;
}
right--;
}
// 从left开始往右寻找 > pivot元素
while(left < right)
{
if(arr[left] > pivot)
{
break;
}
left++;
}
// left找到了大于pivot的，right找到了小于pivot的，交换
swap(arr, left, right);
}
// 到此处，左右游标相遇，交换pivot和arr[left]
swap(arr, i, left);
// 递归pivot左右序列
QuickSortRec(arr, i, left - 1);
QuickSortRec(arr, left + 1, j);
}
int main()
{
int arr[] = {2, 12, 23, 6, 89, 1, 2, 3, 7, 6, 5};
int len = sizeof(arr)/sizeof(arr[0]);
QuickSort(arr, 0, len - 1);
for(auto& v : arr)
{
cout<<v<<" ";
}
return 0;
}
Java代码实现
public class TestSort {
public static void main(String[] args) {
int[] arr = {12333, 34, 2, 1, 3, 5, 64, 2, 9, 12, 4, 8};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.println(i);
}
}
/*
arr: 待排序数组
left: 排序起始位置
right: 排序终止位置
*/
private static void quickSort(int[] arr, int left, int right) {
// ##################################### 分段开始 ####################################
if (left > right || arr == null || arr.length == 0) {
return;
}
int pivot = arr[left];//以左边界的值为基准
int i = left;
int j = right;//使用局部变量接收参数
while (i != j) { //当i = j时表示已经排序好（即基准点左侧都小于基准点，基准点右侧都大于基准点）
while (arr[j] >= pivot && i < j) { //从右往左找小于基准点的数
j--;
}
while (arr[i] <= pivot && i < j) { //从左往右找大于基准点的数
i++;
}
if (i < j) { //寻找到的大于/小于基准点的下标还没有相遇，交换两个的位置
swap(arr, i, j);
}
}
//代码到这，即表示 i, j 已经相遇了
//将基准数归位
swap(arr, left, i);
// ##################################### 分段结束 ####################################
// ##################################### 递归开始 ####################################
quickSort(arr, left, i - 1);//递归对左侧子数组排序
quickSort(arr, i + 1, right);//递归对右侧子数组排序
// ##################################### 递归结束 ####################################
}
//交换数组arr中下标from和to的元素
private static void swap(int[] arr, int from, int to) {
if (from < 0 || from >= arr.length || to < 0 || to >= arr.length) return;
int tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}
}
快排的思想可以总结为：冒泡 + 二分 + 递归分治。
复杂度、稳定性
时间复杂度：O(nlogn)。
空间复杂度：O(nlogn)。
稳定性：不稳定。
为什么一定要从右边开始呢
如以上的程序中，我们在以基准数交换数时，是先从右边开始（j）：
while (arr[j] >= pivot && i < j) { //从右往左找小于基准点的数
j--;
}
while (arr[i] <= pivot && i < j) { //从左往右找大于基准点的数
i++;
}
可不可以从左边开始呢：
while (arr[i] <= pivot && i < j) { //从左往右找大于基准点的数
i++;
}
while (arr[j] >= pivot && i < j) { //从右往左找小于基准点的数
j--;
}
实测发现，这样是不行的。
想象数组{6, 1, 2, 7, 9}，以6为基准数进行快速排序。
- 从左侧开始探索
先从左边开始探索，i将落在7的位置；再从右侧探索，j也将落在7的位置。
此时交换基准数和i指向的数7，数组变成{7, 1, 2, 6, 9}。
考察这个数组，基准数6左边的数并不全是小于基准数的，第一个位置上的7就是比6大的。
- 从右侧开始探索
先从右边开始探索，j将落在2上；再从左侧探索，i也将落在i上。
此时交换基准数和i指向的数2，数组变成{2, 1, 6, 7, 9}。
考察这个数组，基准数6左侧的都比6小，右侧的都比6大。
形而上一点，如果选取最左侧的数arr[left]作为基准数，从最右侧开始探索可以保证当i,j相遇时，i对应的数是小于基准数的，此时交换基准数和i对应的数可保证基准数左侧的数都小于基准数。而如果从左侧开始探索，则当i,j相遇时i对应的数是大于基准数的，此时交换基准数和i对应的数就无法满足基准数左侧的值都小于基准数。
