归并排序代码实现【递归实现+迭代实现】

野性酷女 2022-05-26 12:58 240阅读 0赞

**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));
    		
    	}
    
    }