归并排序 java（分治法）

以你之姓@ 2022-05-31 07:36 261阅读 0赞

# 归并排序： #

归并排序是将给定的数列，尽可能地数量相同的两个数列。然后通过递归调用进行排序，排序完毕后的，将两个已经排好序的数列合并为一个数列，完成最终的排序。

![70][]

### 算法将数列对半分割，一直分割到数列只剩下一个数为止，之后再将排列好的数组合并到一个完整的排列好的数列。归并排序分割简单，而且效率也很高，分割的时间复杂度为O(1);但是合并的过程较为复杂，单独过程将耗费O（n）； ###

最终的时间复杂度为O（nlogn）

public class Main {
    	/*
    	 * a   待排序的数组
    	 * s   待排序数组的起始下标
    	 * e   待排序数组的结束坐标
    	 * tmp 保存数据的数组
    	 * 
    	 */
    	
    	
    	public static void MergeSort(int a[],int s,int e,int tmp[]) {
    		if(s < e) {
    			int m = s+(e-s)/2;//把数组递归分割
    			MergeSort(a,s,m,tmp);
    			MergeSort(a,m+1,e,tmp);
    			Merge(a,s,m,e,tmp);
    		}
    	}
    	//将左右有序的序列   归并在一起  成为新的一个有序的数组
    	//m表示分割下标；
    	public static void Merge(int a[],int s,int m,int e,int tmp[]) {
    		int pb = 0;
    		int p1 = s;//记录s到m  的下标
    		int p2 = m+1;//记录s+1到e  的坐标
    		//分割后的两段数组排序 ， 保存到tmp数组中，
    		while(p1 <= m && p2 <= e) {
    			if(a[p1] < a[p2])
    				tmp[pb++] = a[p1++];
    			else
    				tmp[pb++] = a[p2++];
    		}
    		while(p1<=m)
    			tmp[pb++] = a[p1++];
    		while(p2<=e)
    			tmp[pb++] = a[p2++];
    		for (int i = 0; i < e-s+1; i++) 
    			a[s+i]=tmp[i];
    	}
    	//主方法：
    	public static void main(String[] args) {
    		int[] a = {36,27,43,9,3,82,10};
    		int[] tmp = new int[a.length];
    		MergeSort(a,0,6,tmp);
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i]+",");
    		}
    	}
    }

不对之处，请指教！

[70]: /images/20220531/a9d7aadc9a6548cea08d33d70ae6fd77.png