归并排序详解

淡淡的烟草味﹌ 2022-08-21 02:20 119阅读 0赞

public class MergeSort {
    	
    	public static void main(String[] args){
    		debug();
    	}
    	
    	public static void debug(){
    		int n = (int)(Math.random() * 100);
    		int a[] = new int [n];
    		
    		for(int i=0; i<n; i++){
    			a[i] = (int)(Math.random() * 200);
    		}
    		
    		mergeSort(a, 0, n);
    		
    		for(int i=0; i<n; i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    	/**
    	 * 归并排序
    	 * 原理：可以分为两个部分，第一个部分是划分数组，当数组划分到长度为1的时候可以看成是一个有序的数组，第二个部分是将两个有序的数组合并成一个有序的数组。
    	 * @param a 待排序数组
    	 * @param l 数组起始坐标
    	 * @param r 数组终止坐标+1
    	 */
    	public static void mergeSort(int a[], int l, int r){
    		int m = (l + r)/2;	//数组中间坐标
    		if(r-l > 2){	//当数组中元素超过3个的时候进行划分。
    			mergeSort(a, l, m);
    			mergeSort(a, m, r);
    		}
    		
    		//上面是划分部分，下面是排序部分
    		
    		int pl = l, pm = m, bi = 0;	//pl,pm作为标兵，待排序的两个有序数组为 a[ [pl,m) ] 和   a[ [pm,r) ]注意开闭区间。
    		int b[] = new int[r-l];	//排序后的结果保存在数组b中
    		
    		//有序数组排序思想：比如两个有序数组为   1 3 5  和  2 4 6,
    		//比较1和2, 1<2，把1放到数组b中，此时剩下 3 5 和 2 4 6
    		//再比较3和2,3>2，把2放到数组b中，此时剩下3 5 和 4 6，再依次比较...
    		
    		while(pl<m || pm<r){//结束条件是，两个数组元素都取出来完了。
    			if((pm>=r || a[pl]<a[pm]) && (pl<m)){//当两个数组元素没取出来完时，如果右数组的元素取出来完了，或者 （左数组不为空，并且左数组的元素比右数组元素小）
    				b[bi++] = a[pl++];//则把左数组元素放入b数组中。
    			}else{
    				b[bi++] = a[pm++];//其他的情况 则把右数组元素放入数组b中
    			}
    		}
    		//将排序结果返回数组a
    		for(int i=0; i<b.length; i++){
    			a[i+l] = b[i];
    		}
    	}
    
    }