java数据结构排序之归并排序实现

<span style="font-family:Times New Roman;font-size:18px;"><span style="white-space:pre">	</span>static void mergeSort(int[] dataList,int l,int mid,int r){
		int[] temp = new int[r-l+1];
		int i=l,j=mid+1,k;
		//使用temp来暂存有序的元素
		for (k=0; i<=mid && j<=r; k++) {
			if(dataList[i]<=dataList[j]){
				temp[k] = dataList[i++];
			}else{
				temp[k] = dataList[j++];
			}
		}
		
		if(i<=mid){
			while(i<=mid){
				temp[k++] = dataList[i++];
			}
		}else{
			while(j<=r){
				temp[k++] = dataList[j++];
			}
		}
		
		for (i = l,k=0; i <= r; i++) {
			dataList[i] = temp[k++];
		}
		print(dataList,l,r);
	}
	//对数组进行分割与合并
	static void mSort(int[] dataList,int l, int r){
		if(l<r){
			int mid = (l+r)/2;
			mSort(dataList, l, mid);
			mSort(dataList, mid+1, r);
			mergeSort(dataList,l,mid,r);
		}
	}
	
	static void print(int[] dataList,int l,int r){
		for (int j = 0; j < dataList.length; j++) {
			if(j==l){
				System.out.print("|");
				System.out.print(dataList[j]+"  ");
			}else if(j==r){
				System.out.print(dataList[j]);
				System.out.print("|   ");
			}else
				System.out.print(dataList[j]+"  ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int[] dataList = {13,65,97,76,38,27,49,10,0};
		mSort(dataList,0,dataList.length-1);
	}</span>

归并排序需要注意的是一个分割过程与合并过程，分割过程保证待合并的两个序列都是相对有序的，这样保证归并时候的有序性，关于归并时候的存储，可以再原数组的基础上交换元素，但是比较简单的方法是，生成额外的数组来存储两个序列的合并有序序列，最后再把这个额外数组的值赋还给原数组。。。。