当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-归并排序

发表于: 2011-12-14   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] a={20,1,3,8,5,9,4,25}; mergeSort(a,0,a.length-1); System.out.println(Arrays.to
import java.util.Arrays;


public class MergeSort {

	
	public static void main(String[] args) {

		int[] a={20,1,3,8,5,9,4,25};
		mergeSort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}

	public static void mergeSort(int[] a,int first,int last){
		int len=a.length;
		if(first>=last)return;
		if(first<last){
			//int mid=(first+last)/2;
			//to avoid overflow,you should do it like this:
			int mid=(first&last)+((first^last)>>1);
			int[] temp=new int[len];
			mergeSort(a,first,mid);
			mergeSort(a,mid+1,last);
			mergeTwoArray(temp,a,first,mid,last);
		}
	}
	
	public static void mergeTwoArray(int[] temp,int[] a,int first,int mid,int last){
		int i=first;
		int j=mid+1;
		int k=0;
		while(i<=mid&&j<=last){
			if(a[i]<a[j]){
				temp[k]=a[i];
				i++;
			}else{
				temp[k]=a[j];
				j++;
			}
			k++;
		}
		while(i<=mid){
			temp[k++]=a[i++];
		}
		while(j<=last){
			temp[k++]=a[j++];
		}
		//System.arraycopy(src, srcPos, dest, destPos, length);   
		//at first,i write it like this :   
		//System.arraycopy(temp, 0, a, 0, temp.length);   
		//I can't get it right until I do it like this:   
		System.arraycopy(temp, 0, a, first, last-first+1);  
                //System.arraycopy(temp, 0, a, first, k);//it also works
	}
}


java-归并排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号