当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
我的代码执行环境: 操作系统:OS X Yosemite python版本2.7.6 微信公众平台:今天做了没 归并排序
算法思想 归并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序的列分为若干个
<img src="http://img.it610.com/image/product/cf7
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一
概要 本章介绍排序算法中的归并排序。内容包括: 1. 归并排序介绍 2. 归并排序图文说明 3. 归并排序
归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and
归并排序是分治算法的一个典型的体现: 将原问题分解为若干的子问题进行求解就可以了。 分治算法的步
图示 算法描述 把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列 申请空间
采用分治的思想 以O(NlogN)最坏的情形运行时间运行 如果对merge的每个递归调用都采用局部声明一个临
归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。常见
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号