网站链接优化,做鲜榨果汁店网站,做网站数据需求分析,做医疗器械网站归并排序
归并排序#xff08;任何一个递归#xff09;如果不懂可以画一个树状结构去帮助自己去理解。
核心排序方法为Merger
public class 归并排序 {public static void main(String[] args) {int[] arr1 {3, 1, 2, 2, 5, 6};int[] arr2 Arrays.copyOf(arr1, arr1.len…归并排序
归并排序任何一个递归如果不懂可以画一个树状结构去帮助自己去理解。
核心排序方法为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.对比左右两个区间再进行排序* 递归过程当 LR 时停止也就是当数组被二分为只有一个数时停止* 这时他的上层只有两个数调用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的小和为13 4、2的小和为 1、5的小和为1342 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 - p11 : 0;//逆序对问题//res arr[p1] arr[p2] ? (R-p21)*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[Li] 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)
