### 1.2 随机快排
快速排序程序的整体结构也是递归的，其主要借助一个Partition过程完成排序工作；Partition过程的定义如下：
> 给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
>
> 要求：空间复杂度为O(1)，时间复杂度为O(n)
完成Partition过程只需要两个指针，一个指针用于遍历数组的元素，一个指针用来指向小于等于数组区域的最右边的下标leftBorder，当发现arr\[i\] < num的时候，交换leftBorder+1和i位置的值。
~~~
public static int partition(int[] nums, int num) {
int leftBorder = 0;
int i = 0;
while (i < nums.length) {
if (nums[i] <= num) {
// 与左边界的第一个值交换
swap(nums, leftBorder++, i);
}
i++;
}
return leftBorder - 1;
}
~~~
可以Partition进一步优化，将数组arr根据num分为三个区域，小于左边，等于中间，大于右边；这就是经典的荷兰国旗问题，完成该过程需要两个指针，一个指针指向小于等于数组的右边界leftBorder，一个指针指向大于数组的左边界rightBorder，其初始化分别为：leftBorder=0，rightBorder=arr.length；算法流程如下：
* 当arr\[i\] == num，i++；
* 当arr\[i\] < num，arr\[i\]与小于区域右一个交换，小于区域右扩，i++；
* d当arr\[i\] > num，arr\[i\]与大于区域左一个交换，大于区域左扩，i原地不动（这是因为需要重新判断新换过来的元素是否满足条件）
与partition过程不同的是，荷兰国旗问题返回等于区域左右两个边界的位置。
~~~
public static int[] netherlandsFlag(int[] nums, int num, int L, int R) {
if (L > R) {
return new int[]{-1, -1};
}
if (L == R) {
return new int[]{L, R};
}
int leftBorder = L - 1, rightBorder = R + 1;
int i = L;
while (i < rightBorder) {
if (nums[i] == num) {
i++;
} else if (nums[i] < num){
// 扩充小于数组
swap(nums, i++, ++leftBorder);
} else {
// 扩充大于数组
swap(nums, i, --rightBorder);
}
}
return new int[]{leftBorder + 1, rightBorder - 1};
}
~~~
荷兰国旗问题过程与partition过程相比用于快排可以减少递归的次数。
**快排1.0**
选择最后一个元素最为partition过程的基准元素，对数组分成大于x的组和小于等于x的组，这个过程就可以确定x在排序过程中的位置。之后在从该位置进行左右递归。
~~~
public static void quickSort1(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
process1(nums, 0, nums.length - 1);
}
public static void process1(int[] nums, int L, int R) {
if (L >= R) {
return;
}
// 选取nums[R]作为基准元素
int mid = partition(nums, nums[R], L, R);
process1(nums, L, mid - 1);
process1(nums, mid + 1, R);
}
~~~
**快排2.0**
利用荷兰国旗过程，将数组分为三组，可以一次性确定相等数值的位置，较少递归次数，但是时间复杂度任然是不变的。
~~~
/**
* 利用荷兰国旗过程的快排
* @param nums
*/
public static void quickSort2(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
process2(nums, 0, nums.length - 1);
}
public static void process2(int[] nums, int L, int R) {
if (L >= R) {
return;
}
int[] ints = netherlandsFlag(nums, nums[R], L, R);
process2(nums, L, ints[0] - 1);
process2(nums, ints[1] + 1, R);
}
~~~
快排1.0和快排2.0如果按照最差的情况，即数组本身就是排好序的，其时间复杂度为O(n^2)。
**快排3.0**
随机选一个数作为划分值，然后将该值与最后一个值交换。
~~~
/**
* 随机快排
* @param nums
*/
public static void quickSort3(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
process3(nums, 0, nums.length - 1);
}
public static void process3(int[] nums, int L, int R) {
if (L >= R) {
return;
}
// 随机选择一个元素
int randomIndex = (int)(Math.random() * (R - L + 1)) + L;
int[] ints = netherlandsFlag(nums, nums[randomIndex], L, R);
process3(nums, L, ints[0] - 1);
process3(nums, ints[1] + 1, R);
}
~~~
这种情况下好的情况的时间复杂度为：
T(n) = 2 \* T(n/2) + O(n)，由主方法可知其时间复杂度为O(nlgn)。用概率来计算其时间复杂度：最后得到平均时间复杂度为：O(nlgn)。不用最差情况考虑就是因为程序在运行的时候是随机选择，最差情况发生的概率并不大。
随机快排的时间复杂度分析：
1. 划分值越靠近中间，性能越好，越靠近两边，性能越差。
2. 随机选一个数进行划分的目的就是让好情况和差情况都变成概率时间。
3. 把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都为1/N。
4. 把所有的情况都考虑下去，时间复杂度就是这种概率模型下的长期期望，通过数学公式的推导，其时间复杂度为O(nlgn)，空间复杂度为O(lgn)。
小验证：
~~~
public static void main(String[] args) {
Random random = new Random();
// 使用partition过程的快排时间
long start = System.currentTimeMillis();
int[] nums = new int[100000];
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < nums.length; j++) {
nums[j] = random.nextInt(100000);
}
quickSort1(nums);
}
long end = System.currentTimeMillis();
System.out.println("partition过程的快排时间为：" + (end - start) / 1000.0 + "s");
// 使用netherlandsFlag过程的快排时间
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < nums.length; j++) {
nums[j] = random.nextInt(100000);
}
quickSort2(nums);
}
end = System.currentTimeMillis();
System.out.println("netherlandsFlag过程的快排时间为：" + (end - start) / 1000.0 + "s");
// 使用随机过程的快排时间
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < nums.length; j++) {
nums[j] = random.nextInt(100000);
}
quickSort3(nums);
}
end = System.currentTimeMillis();
System.out.println("随机快排过程的快排时间为：" + (end - start) / 1000.0 + "s");
}
~~~
结果：
~~~
partition过程的快排时间为：106.185
netherlandsFlag过程的快排时间为：118.341
随机快排过程的快排时间为：130.55
~~~
结论：在数据本身就是均匀的情况下，partition过程反倒更合适！
但是如果数组原本就是逆序的，随机快排的优势就可以大大的显示出来
~~~
partition过程的快排时间为：352.794s
netherlandsFlag过程的快排时间为：1017.239s
随机快排过程的快排时间为：6.513s
~~~
