快速排序本质是寻找基准值在数组中索引的过程。
实际操作是选取一个基准值，遍历数组，将小于基准值的数放到数组左边，等于基准值的数放到数组中间，大于基准值的数放到数组右边，那么，中间等于区域就是基准值的索引位置，也就是基准值已经排好序。然后小于区域继续选取自己的基准值，大于区域继续选取自己的基准值，继续根据基准值划分区域，递归这个过程，直到整个数组有序。
二、实现过程与荷兰国旗问题荷兰国旗问题跟快速排序的内部操作一样，我们可以先从荷兰国旗问题入手。
荷兰国旗：
（荷兰国旗是三色的，分开的3个区域）
荷兰国旗问题：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。
解答：题目要求额外空间复杂度为O(1)，说明我们只能在原数组上操作，如果用辅助数组，则会导致空间复杂度上升到O(N)。实现步骤：
1、将指定num与数组最后一位交换位置。
2、不妨定义数组小于区域的边界为lessBorder，数组大于区域的边界为moreBorder。
3、遍历数组：
如果当前位置i的值比num小，则将"小于区域"后一位的值与当前值交换，并且"小于区域"边界向右移动一位，即lessBorder自增1；
如果当前位置i的值比num大，则将"大于区域"前一位的值与当前值交换，并且"大于区域"边界向左移动一位，即moreBorder自减1；
如果当前位置i的值等于num，则什么都不做，当前位置右移一位。
4、持续上一步，直到当前位置等于"大于区域"边界。
java代码实现：
public static void partition(Integer[] arr, int L, int R) {
// "小于区域"的边界
int lessBorder = L - 1;
// "大于区域"的边界（本来"大于区域"的边界应该是R+1,但R位上已被基准值占据，所以"大于区域"边界是R)
int moreBorder = R;
// 当前位置
int i = L;
// 如果当前位置等于"大于区域"的边界，则说明整个区间的数已被遍历完
while(i < moreBorder) {
// arr[R]表示基准值
// 如果当前位置的值小于基准值，则"小于区域"的下一个值与当前位置值交换，并且"小于区域"边界向右移一位，当前位置i自增一位
if(arr[i] < arr[R]) {
DataStore.swap(arr, ++lessBorder, i++);
}
// 如果当前位置的值大于基准值，则"大于区域"的前一个值与当前位置值交换，并且"大于区域"边界向左移一位，当前位置i不变
else if(arr[i] > arr[R]) {
DataStore.swap(arr, --moreBorder, i);
}
// 如果当前位置的值等于基准值，什么都不做，当前位置i自增一位
else {
i++;
}
}
// 当前基准值在区间最后一个位，将基准值与"大于区域"首位交换，区间变得整体有序
DataStore.swap(arr, moreBorder, R);
}
三、实现步骤
快速排序的实现步骤就是递归荷兰国旗问题的过程，划分好一次区域后，不断在"小于区域"和"大于区域"中选定基准值，继续划分区域，找到基准值的索引值。
假设数组中有n个数，那么指定n个基准值，进行了n次比较排序，所以，时间复杂度是O(N ^ 2)。但是，如果我们的基准值是随机选取，使每种情况出现的概率都为N分之一，那么时间复杂度数学期望值为O(NlogN)。(证明过程不需掌握，了解即可)
实现步骤图示：
java代码实现：
// 快速排序
public class QuickSort {
public static void main(String[] args) {
Integer[] arr = DataStore.getData();
String source = "";
for(int i = 0; i < arr.length; i++) {
source += arr[i] + " ";
}
System.out.println("原数组：" + source);
QuickSort.quickSort(arr, 0, arr.length - 1);
String res = "";
for(int i = 0; i < arr.length; i++) {
res += arr[i] + " ";
}
System.out.println("排序后：" + res);
}
// 快速排序
public static void quickSort(Integer[] arr, int L, int R) {
if(L < R) {
// 随机选取一个基准值，将区间最后一个值与基准值交换位置
DataStore.swap(arr, L + (int)Math.random()*(R - L + 1), R);
Integer[] p = partition(arr, L, R);
// 小于区域
quickSort(arr, L, p[0] - 1);
// 大于区域
quickSort(arr, p[1] + 1, R);
}
}
public static Integer[] partition(Integer[] arr, int L, int R) {
// "小于区域"的边界
int lessBorder = L - 1;
// "大于区域"的边界（本来"大于区域"的边界应该是R+1,但R位上已被基准值占据，所以"大于区域"边界是R)
int moreBorder = R;
// 当前位置
int i = L;
// 如果当前位置等于"大于区域"的边界，则说明整个区间的数已被遍历完
while(i < moreBorder) {
// arr[R]表示基准值
// 如果当前位置的值小于基准值，则"小于区域"的下一个值与当前位置值交换，并且"小于区域"边界向右移一位，当前位置i自增一位
if(arr[i] < arr[R]) {
DataStore.swap(arr, ++lessBorder, i++);
}
// 如果当前位置的值大于基准值，则"大于区域"的前一个值与当前位置值交换，并且"大于区域"边界向左移一位，当前位置i不变
else if(arr[i] > arr[R]) {
DataStore.swap(arr, --moreBorder, i);
}
// 如果当前位置的值等于基准值，什么都不做，当前位置i自增一位
else {
i++;
}
}
// 当前基准值在区间最后一个位，将基准值与"大于区域"首位交换，区间变得整体有序
DataStore.swap(arr, moreBorder, R);
// 返回"等于区域"的左右边界索引
Integer[] res = {lessBorder + 1, moreBorder};
return res;
}
}
DataStore工具类
public class DataStore {
// 随机获取10个整数
public static Integer[] getData() {
List list = new ArrayList();
for(int i = 0; i < 10; i++) {
double d = Math.random();
list.add((int)(d*10));
}
Integer[] arrays = new Integer[list.size()];
list.toArray(arrays);
return arrays;
}
// 数组中两数交换
public static void swap(Integer[] array, int i, int j) {
if(array != null && i < array.length && j< array.length) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
