1、归并排序--递归实现
2、归并排序--迭代实现
1、归并排序--递归实现
package aa; import java.util.Arrays; public class MergeSort2 { //分解 public static void sort(int[] arr,int low,int high){ if(low<high){ int mid=(low+high)/2; sort(arr,low,mid);//左边排序+分解 sort(arr,mid+1,high);//右边排序+分解 merge(arr,low,mid,high);//合并+排序 } } //合并 public static void merge(int[] arr,int low,int mid,int high)//合并 { //获取左边的元素 + 获取右边的元素 大小的判断 int i=low;//左边开始下标 int j=mid+1;//右边开始下标 int k=0;//临时数组下标 int temp[]=new int[high-low+1];//临时数组存放元素 while(i<=mid && j<=high){ if(arr[i]<arr[j]){ temp[k++]=arr[i++];//左边的元素小，放入 } else{ temp[k++]=arr[j++];//右边的元素小，放入 } } //剩余元素判断 while(i<=mid){ temp[k++]=arr[i++];//左边元素 } while(j<=high){ temp[k++]=arr[j++];//右边元素 } System.out.println("此时temp:"+Arrays.toString(temp)); //改变原来的arr数组 //如何覆盖元素的问题！！！！！！！！！！！！！！ //将区间为low,high的元素进行覆盖 [ ] //原因low~high区间的元素，在此处进行了排序 k=0; while(low<=high){ arr[low++]=temp[k++]; } // t = 0; // //将temp中的元素全部拷贝到原数组中 // while(left <= right){ // arr[left++] = temp[t++]; // } } public static void main(String[] args) { int[] arr={5,7,1,9,2,6,3,4}; System.out.println("111排序前："+Arrays.toString(arr)); sort(arr,0,arr.length-1); System.out.println("111排序后："+Arrays.toString(arr)); } }
2、归并排序--迭代实现
package sort; import java.util.Arrays; //迭代的方式进行 归并排序 public class IterationMergeSort { //迭代 /* //第一次 比较两个元素 从 low 到high ,即两个为一组，进行比较 步长为1 //第二次 比较四个元素 从 low 到high ,即四个为一组，进行比较 步长为2 //第三次 比较八个元素 从 low 到high ,即八个为一组，进行比较 步长为4 //...... //第n次 比较2*n个元素 从 low 到high ,即2*n个为一组，进行比较 步长为n */ public static void sort(int[] arr,int low,int high){ //sort(arr,0,arr.length-1); int left_low=0,left_high=0;//一组元素的左边部分 int right_low=0,right_high=0;//一组元素的右边部分 int temp[] = new int[high]; for(int i=low;i<high;i=2*i){//一次迭代，步长增长 //从 数组的 low 到 high 位置，依次进行比较，补偿为n，一组元素个数为2*n进行比较 // for(;right_high<high;left_low=right_high){//错误 // for(left_low=0;right_high<high-i;left_low=right_high){ for(left_low=0;left_low<high-i;left_low=right_high){//left_low=right_high 从下一组中，开始进行比较 //此处，变量名字写错 // left_high=low+i;//左边结束 // right_low=low+i;//右边开始 // right_high=right_low+i;//右边结束 left_high=left_low+i;//左边结束 right_low=left_low+i;//右边开始 right_high=right_low+i;//右边结束 if(right_high>high){ right_high=high;//确保right_high小于等于high } //int temp[] =new int[right_high-left_low+1];//创建临时数组存放排好序的元素 int k=0;//临时数组的下标 //比较过程，类似于合并排序的 递归的比较 while(left_low<left_high && right_low <right_high){ if(arr[left_low]<arr[right_low]){//左边的 < 右边的 temp[k++]=arr[left_low++]; } else{ temp[k++]=arr[right_low++]; } } //未比较完的，则进行补充即可 while(left_low < left_high){ temp[k++]=arr[left_low++];//补充左边 } // 上面循环结束的条件有两个，如果是左边的游标尚未到达，那么需要把 // 数组接回去，可能会有疑问，那如果右边的没到达呢，其实模拟一下就可以 // 知道，如果右边没到达，那么说明右边的数据比较大，这时也就不用移动位置了 // while(right_low <right_high){ // temp[k++]=arr[right_low++];//补充右边 // } System.out.println("temp::"+Arrays.toString(temp)); //将排好序的元素，进行赋值到原来的数组中 while(k>0){//将 low ~ high区间的元素进行排序 arr[--right_low]=temp[--k]; } } } } public static void main(String[] args) { // int[] arr={5,7,1,9,2,6,3,4}; int arr[] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 }; System.out.println("迭代合并--排序前："+Arrays.toString(arr)); sort(arr,1,arr.length); // sort(arr,0,arr.length-1); System.out.println("迭代合并--排序后："+Arrays.toString(arr)); } }
