归并排序(JAVA语言)

public class merge {

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		int a[]= new int[20];

		int b[]=new int[a.length];

		for(int i=0;i<a.length;i++) {

			a[i]=(int) (Math.random()*100);

			System.out.print(a[i]+" ");

		}

		System.out.println();

		sort(a,b,0,a.length-1);

		for(int i=0;i<a.length;i++) {

			System.out.print(a[i]+" ");

		}

	}

	private static void sort(int[] a,int []b,int left,int right) {

		// TODO Auto-generated method stub

		if(left<right){

			int mid=(left+right)/2;

			sort(a,b,left,mid);       //对左半部分进行排序

			sort(a,b,mid+1,right);    //对右半部分进行排序

			merge(a,b,left,right);    //归并

		}

	}

	private static void merge(int[] a, int b[],int left, int right) {

		// TODO Auto-generated method stub

		copy(a,b,left,right);//将a数组中元素copy到b中

		int rs=(left+right)/2+1;//右侧起始指针

		int le=rs-1;//左侧结束指针

		int i=left;//a数组指针，指向代排元素起始位置

		while(left<=le&&rs<=right)//左边右边都不为空

			if(b[left]>b[rs]) {

				a[i++]=b[rs++];

			}

			else {

				a[i++]=b[left++];

			}

		while(left>le&&rs<=right) {

			//左边为空（其实这里可以去掉，因为原数组的元素位置已经正确）

			a[i++]=b[rs++];

		}

		while(left<=le&&rs>right) {//右边为空

			a[i++]=b[left++];

		}

	}

	private static void copy(int[] a, int[] b, int left, int right) {

		// TODO Auto-generated method stub

		for(int i=left;i<=right;i++) {

			b[i]=a[i];

		}

	}

}
巴特西

归并排序(JAVA语言)

最新文章

热门文章
