1 整体思路:
归并排序的整体思想就是分而直至的思想,将整体数组进行二分 然后再进行合并,如下图:
数组拷贝的过程,图解演示2967 -》2679 这个步骤
2 代码解析
package com.cxy.registersever.study; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] a =new int[]{1,3,4,5,7,2}; mergeSort(a); Arrays.stream(a).forEach(System.out::println); } public static void mergeSort(int[] a){ int[] arr =new int[a.length]; // 创建零时数组 避免重复创建数组 sort(a,0,a.length-1,arr); } private static void sort(int[] a, int left, int right, int[] arr) { if (left<right){ int mid =(left+right)/2; sort(a,left,mid,arr); // 左边归并 sort(a,mid+1,right,arr); // 右边归并 为啥是mid+1 mid值已经进行了处理 所以对右边时候是mid+1 merge(a,left,mid,right,arr); // 合并 } } private static void merge(int[] a, int left, int mid, int right, int[] arr) { int i =left; // 左边的起始位置 int j =mid +1; // 右边的起始位置 int k =0; // 零时数组的索引位置 while(i<=mid&&j<=right){ // 判断条件 left 的终值 不可以超过mid,mid+1 位置的值不可以超过right if (a[i]<=a[j]){ arr[k++] =a[i++]; // 将小的数据拷贝至零时数组 索引位置右移,零时数组位置也右移动 }else{ arr[k++] =a[j++];// 将小的数据拷贝至零时数组 索引位置右移,零时数组位置也右移动 } } while (i<=mid){ // 如果左边数据多,拷贝至数组最外边 arr[k++] =a[i++]; } while(j<= right){ // 如果右边数据多,拷贝至数组最外边 arr[k++] =a[j++]; } k =0; // 将零时数据组中的数据拷贝至原数组 零时数组中的数据会替代,所以不担心数组重复问题 while(left<= right){ // 判断条件为啥left<= right 是循环终止条件,代表拷贝完毕 a[left++] =arr[k++]; } } }
3 题解:
给定两个大小分别为 m
和 n
的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的 中位数 。(leetcode4)
处理方法1 :进行归并排序,然后找出中位数
看代码如下:
package com.cxy.registersever.study; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] a =new int[]{1,3,4,10,7,2}; int[] b =new int[]{6,8,9}; int[] c =new int[a.length+b.length]; for (int i =0;i<a.length+b.length;i++){ //9 if (i<=a.length-1){ c[i] =a[i]; }else{ c[i] =b[i-a.length]; } } mergeSort(c); Arrays.stream(c).forEach(System.out::println); System.out.println(c[(a.length+b.length)/2]); } public static void mergeSort(int[] a){ int[] arr =new int[a.length]; sort(a,0,a.length-1,arr); } private static void sort(int[] a, int left, int right, int[] arr) { if (left<right){ int mid =(left+right)/2; sort(a,left,mid,arr); // 左边归并 sort(a,mid+1,right,arr); // 右边归并 为啥是mid+1 mid值已经进行了处理 所以对右边时候是mid+1 merge(a,left,mid,right,arr); // 合并 } } private static void merge(int[] a, int left, int mid, int right, int[] arr) { int i =left; // 左边的起始位置 int j =mid +1; // 右边的起始位置 int k =0; // 零时数组的索引位置 while(i<=mid&&j<=right){ // 判断条件 left 的终值 不可以超过mid,mid+1 位置的值不可以超过right if (a[i]<=a[j]){ arr[k++] =a[i++]; // 将小的数据拷贝至零时数组 索引位置右移,零时数组位置也右移动 }else{ arr[k++] =a[j++];// 将小的数据拷贝至零时数组 索引位置右移,零时数组位置也右移动 } } while (i<=mid){ // 如果左边数据多,拷贝至数组最外边 arr[k++] =a[i++]; } while(j<= right){ // 如果右边数据多,拷贝至数组最外边 arr[k++] =a[j++]; } k =0; // 将零时数据组中的数据拷贝至原数组 零时数组中的数据会替代,所以不担心数组重复问题 while(left<= right){ // 判断条件为啥left<= right 是循环终止条件,代表拷贝完毕 a[left++] =arr[k++]; } } }
方法2 整个数组的中位数 说明需要循环m+n/2次就好了,因为两个数据是有序的
public static int get(int[] a,int[] b){ // 定义数组a下表位置 b数组下标位置 left接收上一个数,right接收下一个数据 int i =0; int j =0; int left =-1; int right =-1; int mid =(a.length+b.length)/2; for (int k =0;k<= mid;k++){ left =right; // 判断条件 i<=a.length 循环位置不可以超过数组 // 当数组a的下标不超过a的值,a[i]<=b[j] 取数组a中的值,还要就是b数组没有值了 if (i<a.length&&(j>b.length||a[i]<=b[j])){ right =a[i++]; }else{ right =b[j++]; } } if ((a.length+b.length)%2 ==0){ return right+left/2; } return right; }