1. 快速排序
快排用到了分治的思想，它的时间复杂度为O(n*logn)，额外空间复杂度为O(logn)，是时间复杂度为O(n*logn)的所有排序算法中最快的排序算法。
注意：快速排序是一种不稳定的排序算法。
2. 荷兰国旗问题（partition）
目标：给定一个数组，并选取数组中的一个数，将数组中所有小于它的数移到这个数左边，所有大于它的数移动到这个数右边。要求采用算法的时间复杂度为O(n)，空间复杂度为O(1)。
思路：设选取的数为num，用一个变量标识小于这个数的边界，一个变量标识大于这个数的边界。
从左到右遍历数组，对于每个访问到的数arr[i]，如果
①arr[i]< num，那么将它和小于区的下一个数交换位置，并使小于区的边界值加一（小于区向右扩充一个位置），然后访问下一个数；
②arr[i]> num，那么将它和大于区的前一个数交换位置，并使大于区的边界值减一（大于区向左扩充一个位置），当前位置不变（换过来的数还没有判断过，因此不能立即访问下一个数）；
③arr[i]== num，直接访问下一个数
反复执行上述过程，直到访问到大于区的边界。
private int[] partition(int[] arr, int L, int R) {
//选定的进行比较的数值，可以随机选择
int num = arr[L];
//左边比num小的区域边界
int less = L - 1;
//右边比num大的区域边界
int greater = R + 1;
// 当前的指针
int index = L;
while (index < greater) {
//把比num大的数换到右边边界去，换过来的数还没有判断过，因此不能立即访问下一个数
if (arr[index] > num) {
swap(arr, index, --greater);
} else if (arr[index] < num) {
swap(arr, index++, ++less);
} else {
index++;
}
}
return new int[]{less + 1, greater - 1};
}
3. 快速排序的实现
快速排序的基本思想是：每趟选取一个基准值num，并采用partition来将小于num的值放在它左侧，大于num的值放在它右侧，然后再对左侧和右侧分别使用partition递归，直到left>=right。
public void quickSort(int[] arr, int L, int R) {
if (arr == null || arr.length < 2 || L >= R) {
return;
}
//对数组进行划分
int[] numIndex = partition(arr, L, R);
quickSort(arr, L, numIndex[0] - 1);
quickSort(arr, numIndex[1] + 1, R);
}
4. 快速排序的时间复杂度与空间复杂度分析
(1)时间复杂度
快速排序的时间复杂度与数组的数据状况有关：当每次partition所选取的数num刚好是数组中的中间大小的数（即num左侧和右侧数的个数相同），那么就是比较好的情况，时间复杂度为O(nlogn)；如果每次pritition所选取的数大于或小于其他所有数，那么就是比较坏的情况，时间复杂度为O(n^2)。
经过大量数据样本的测试，以及概率加权，可以发现快速排序的时间复杂度最终收敛到O(nlogn)
为了减少快速排序受数据状况的影响，可以在每次partition时，采用随机选取的方式来选择基准值num。
(2)空间复杂度
分析方法类似于时间复杂度的分析，也是分好情况和坏情况讨论，并对于所有可能出现的情况进行概率加权求期望。
由partition()和quickSort()部分的代码可知，partition()使用的空间为常数级，而quickSort()所使用的空间取决于要递归多少次。
如果是比较好的情况，即每次选取的数num，大于num和小于num的数的数量相等，则至多需要递归logn次，此时的空间复杂度为O(logn)。
如果是比较坏的情况，即每次选取的数num，其他数要么全小于它，要么全大于它，则需要递归n次，此时的时间复杂度为O(n)。
对所有可能出现的好情况和坏情况进行概率加权求期望，可以得出快速排序的空间复杂度收敛于O(logn)。
综上所述，快速排序的空间复杂度为O(logn)。
