归并排序
归并排序（任何一个递归）如果不懂可以画一个树状结构去帮助自己去理解。
核心排序方法为Merger
public class 归并排序 {
public static void main(String[] args) {
int[] arr1 = {3, 1, 2, 2, 5, 6};
int[] arr2 = Arrays.copyOf(arr1, arr1.length);
process(arr1, 0, arr1.length - 1);
sort(arr2);
}
/**
* 归并排序
* 1.将左边排好序，再将右边排好序
* 2.对比左右两个区间再进行排序
* 递归过程，当 L==R 时停止，也就是当数组被二分为只有一个数时停止，
* 这时他的上层只有两个数，调用merger进行排序
*/
public static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
//获取中点位置,为避免整数溢出现象而不写为(R + L) / 2,
//原因是如果R与L都是int边缘，相加将越界
int mid = L + ((R - L) >> 1);
//左区域排序
process(arr, L, mid);
//右区域排序
process(arr, mid + 1, R);
//对比左右两个区间再进行排序
merger(arr, L, mid, R);
//打印
print(arr, "arr1");
}
/**
* 两个指针，一个指向L（最左索引），一个指向R（最右索引）
* 如果L,R都不越界，对比L,R大小将排好序的数据放入新数组
* 如果其中一个越界，将未越界数组剩余数据放入新数组的后面
*/
private static void merger(int[] arr, int L, int mid, int R) {
int[] help = new int[R - L + 1];
//记录新数组排序到的位置
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
//如果右边越界，左边剩余数据会全部填充到新数组后边
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
public static void sort(int[] arr) {
Arrays.sort(arr);
print(arr, "arr2");
}
public static void print(int[] arr, String a) {
StringBuilder sb = new StringBuilder();
sb.append(a + "= {");
for (int i = 0; i < arr.length; i++) {
if (i > 0) {
sb.append(", ");
}
sb.append(arr[i]);
}
sb.append("}");
System.out.println(sb.toString());
}
}小和问题/逆序对问题（归并排序变种）
小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做数据的小和。
例：数组{1,3,4,2,5} 1的小和为0 、3的小和为 1、4的小和为1+3 = 4、2的小和为 1、5的小和为1+3+4+2 = 10。
逆序对问题：在一个数组中，左边的数如果比右边的数大，则两个数构成一个逆序对，请计算出逆序对的数量。
思考逻辑
正常思维（暴力解法）：小和问题，需要向左寻找比自己小的数，例如：3向前寻找1,4向前寻找1,3。如果是这种情况下数组左边的数每次都需要被遍历一次，没有重复利用其之前搜寻到的数据。
逆向思考：小和问题，正常向左寻找比自己小的数，边为向右寻找比自己大的数。也就是1右边有4个数比自己大，就是4个1、3右边有2个数比自己大，就是2个3、4右边有一个数比自己大，就是一个4、2右边有一个数比自己大也就是一个2.共计16.
在上述过程中我们发现1考虑过之后后面数就无需考虑了，也就是利用到之前的信息了。
小和问题/逆序对问题的关键就是找到逆向思路，根据其能够重复利用信息的特点就可以考虑归并排序。
public class 小和问题/逆序对问题 {
public static void main(String[] args) {
int[] arr = {3, 2, 4, 5, 0};
int[] testArr = Arrays.copyOf(arr, arr.length);
int nums = process(testArr, 0, testArr.length - 1);
System.out.println(nums);
}
public static int process(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int mid = L + ((R - L) >> 1);
//需要左右两边统计和合并统计
return process(arr, L, mid)
+ process(arr, mid + 1, R)
+ merger(arr, L, mid, R);
}
private static int merger(int[] arr, int L, int mid, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
int res = 0;
while (p1 <= mid && p2 <= R) {
//逆序对问题可以转变为，找出左边比当前数大的个数
res += arr[p1] > arr[p2] ? mid - p1+1 : 0;//逆序对问题
//res += arr[p1] <= arr[p2] ? (R-p2+1)*arr[p1] : 0; 小和问题
//按照顺序排序是必须的，这样就可以根据第一个位置的大小快速确认后续数据是否需要统计
//后续数据就可以根据索引进行计算
help[i++] = arr[p2] >= arr[p1] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L+i] = help[i];
}
return res;
}
}快排
荷兰旗问题
给定一个数num，要求将数组划分为三部分，一部分是小于num，一部分是等于num，一部分是大于num。
三指针解法：
当前数称为current，如果current < num，指针1的前一个位置与arr[i]交换位置，指针1向右移动（为什么要交换?因为当current = num时 指针3要向前移动）
如果current = num，那么指针3++
如果current > num,指针2向左移动一个位置，指针2的前一个位置与与i交换位置
指针1划分小于区域，指针2划分大于区域，指针1、2共同划分出来等于区域。指针3的作用是找出等于num的数并跳过，并且指针1、2的交换对象都是指针2.（先交换再移动。写代码的时候要知道指针该怎么移动，这是写代码的重点）
public class 荷兰旗问题 {
public static void main(String[] args) {
int[] arr = {3,2,5,4,4,0,1,9};
int[] copy = Arrays.copyOf(arr, arr.length);
sort(copy,4);
for (int i : copy) {
System.out.print(i+" ");
}
}
public static void sort(int[] arr, int num) {
int less = -1;
int greate = arr.length;
int index = 0;
while(index < greate){
if (arr[index] < num) {
swap(arr, ++less, index++);
}else if(arr[index] == num){
index++;
}else {
swap(arr, index, --greate);
}
}
}
// 交换数组中两个元素的位置
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}快排实现
快排就是在荷兰旗问题上添加排序过程。怎么理解那，荷兰旗问题划分为大于、小于、等于三个区间，数如果处于等于的位置那么这个数在整个有序集合的位置就不会变，利用递归就可以划分出无数个小区间，小区间到只有一个数的时候，那么整个大区间就都有序了
public class 快排 {
public static void main(String[] args) {
int[] arr = {3,2,5,4,4,0,1,9};
int[] copy = Arrays.copyOf(arr, arr.length);
quickSort(copy,0,copy.length-1);
for (int i : copy) {
System.out.print(i+" ");
}
}
public static void quickSort(int[] arr, int L, int R) {
if (L < R) {
//swap在这里随机抽取目标数放入R位置
swap(arr, L + (int) (Math.random()) * (R - L + 1), R);
//分区，需要返回下一次递归划分的区间
int[] partition = partition(arr, L, R);
quickSort(arr,L,partition[0]);
//需要+1的原因是右区间右交换了一个原先在末尾位置的目标数
quickSort(arr,partition[1]+1,R);
}
}
/**
*
* @param L L代表着遍历的索引位置
* 就是荷兰旗问题中的index，这里可以直接使用L代替
* @param R 代表目标数
* 因为随机抽取的目标数会换到最后一个位置，可以使用R代替
*/
public static int[] partition(int[] arr, int L, int R) {
int less = L - 1;
int more = R;
while (L < more) {
if (arr[L] < arr[R]) {
swap(arr, ++less, L++);
} else if (arr[L] == arr[R]) {
L++;
} else if (arr[L] > arr[R]) {
swap(arr, L, --more);
}
}
//将目标数重新交换到等于区间内
swap(arr, more, R);
//返回的数组表示，大于区间与小于区间的边界，目的是为下一次递归提供划分区间信息
return new int[]{less, more};
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}。
核心问题，区间如何划分，也就是如何选出一个目标数。单纯用数组最后一个数作为目标数也可以，但是这样如果遇到{1,2,3,4,5,6,7,8,9}这种顺序的集合那么他的时间复杂度就为O(n^2)。所以为了避免这种情况的发生，目标数在区间内随机抽取，如果是随机抽取的情况下根据数学期望那么时间复杂度就为O(NLogN)
