2.快速排序
Partition过程：
给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边；
要求额外空间复杂度O(1)，时间复杂度O(N)。
思路如下：
Partition过程升级版（荷兰国旗问题）：
给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边；
要求额外空间复杂度O(1)，时间复杂度O(N)。
思路如下：
两种分区实现如下：
public class PartitionAndQuickSort { /* 普通分区： 给定一个数组arr和一个整数num， 请把小于等于num的数放在数组的左边， 大于num的数放在数组的右边 */ public static int partition(int[] arr, int L, int R) { if (L > R) { return -1; } if (L == R) { return L; } int lessEqual = L - 1; int index = L; while (index < R) { if (arr[index] <= arr[R]) { swap(arr, index, ++lessEqual); } index++; } swap(arr, ++lessEqual, R); return lessEqual; } /* 分区升级版：荷兰国旗： 给定一个数组arr和一个整数num 请把小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的右边 */ public static int[] netherlandsFlag(int[] arr, int L, int R) { if (L > R) { return new int[]{-1, -1}; } if (L == R) { return new int[]{L, R}; } int less = L - 1, more = R; int index = L; while (index < more) { if (arr[index] == arr[R]) { index++; } else if (arr[index] < arr[R]) { swap(arr, index++, ++less); } else { swap(arr, index, --more); } } swap(arr, more, R); return new int[]{less + 1, more}; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
快速排序：
快速排序有3种方式：
（1）利用普通分区算法；
（2）利用荷兰国旗算法；
（3）随机选数与最后一个数交换，再利用荷兰国旗算法。
分析时间复杂度：
随机快排的时间复杂度分析：
1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差
2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件
3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N
4)那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望，
时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。
（1）前两种：
最差情况是数组已经有序：
（2）第三种
一般情况是获取到的随机数在数组中间位置附近，就属于较好的情况：
空间复杂度：
最差情况下是O(N)，累加求期望收敛于O(LogN)。
3种快速排序实现如下：
public static void quickSort1(int[] arr) { if (null == arr || arr.length < 2) { return; } process1(arr, 0, arr.length-1); } public static void process1(int[] arr, int L, int R) { if (L >= R) { return; } int M = partition(arr, L, R); process1(arr, L, M - 1); process1(arr, M + 1, R); } public static void quickSort2(int[] arr) { if (null == arr || arr.length < 2) { return; } process2(arr, 0, arr.length-1); } public static void process2(int[] arr, int L, int R) { if (L >= R) { return; } int[] equalArea = netherlandsFlag(arr, L, R); process1(arr, L, equalArea[0] - 1); process1(arr, equalArea[1]+ 1, R); } public static void quickSort3(int[] arr) { if (null == arr || arr.length < 2) { return; } process3(arr, 0, arr.length-1); } public static void process3(int[] arr, int L, int R) { if (L >= R) { return; } swap(arr, (int) (Math.random() * (R + 1)), R); int[] equalArea = netherlandsFlag(arr, L, R); process1(arr, L, equalArea[0] - 1); process1(arr, equalArea[1]+ 1, R); }
总结
归并排序有很多个应用场景，一般应用在数组中左边的数比右边的数满足某个条件时，进行某个操作，都可以在归并的过程中进行解决。
