认识O(NlogN)的排序

归并排序

归并排序（任何一个递归）如果不懂可以画一个树状结构去帮助自己去理解。

核心排序方法为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)