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

MergeSort Algorithm 归并排序 例子

发表于: 2013-12-17   作者:alleni123   来源:转载   浏览次数:
摘要: 摘自 http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html 这个对本人实在是很有难度。。 起初是在java的Collections.sort()的api里面看到, 说是java所使用的排序是修改了的mergesort .- The sorting algorithm is a modified m
摘自 http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html


这个对本人实在是很有难度。。

起初是在java的Collections.sort()的api里面看到, 说是java所使用的排序是修改了的mergesort .- The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).

网上查了一下就看到这个。
拿着纸和比在debug模式里研究了半天,大概明白了那么一点点。

实现代码:
public class Mergesort
{
	private int[] numbers;
	
	
	/**
	 * int[] helper在算法中起到存放数据并和numbers里进行大小比较的作用。
	 */
	private int[] helper;
	
	/**
	 * number是要排序的数组的大小
	 */
	private int number;
	
	public void sort(int[] values){
		this.numbers=values;
		number=values.length;
		this.helper=new int[number];
		mergesort(0,number-1);
	}
	
	private void mergesort(int low, int high){
		//check if low is smaller than high, if not
		//then the array is sorted.
		if(low<high){
			//get the index of the element which is in the middle
			int middle=low+(high-low)/2;
			//sort the left side of the array
			mergesort(low,middle);
			
			//sort the right side of the array
			mergesort(middle+1, high);
			
			//combine them both
			merge(low,middle,high);
		}
	}
	
	
	
	
	private void merge(int low, int middle, int high){
		//copy both parts into the helper array
		for(int i=low; i<=high; i++){
			helper[i]=numbers[i];
		}
		int i=low;
		int j=middle+1;
		int k=low;
		
		//copy the smallest values from either the left or the right
		//side back to the original array
		while(i<=middle&&j<=high){
			//这里进行排序,如果helper[i]和helper[j]根据大小进行位置调整
			//比如helper[0]==3和helper[1]==1,则进入if里面
			//number[1]=helper[0]
			if(helper[i]<=helper[j]){
				numbers[k]=helper[i];
				i++;
			}else{
				numbers[k]=helper[j];
				j++;
			}
			
			//k代表numbers的索引,是一定会加1的。因为这里就是要将helper[i]
			//和helper[j]做比较。最终将小的那个值放入numbers[k]
			k++;
		}
		
		//copy the rest of the left side of the array into the target array
		while(i<=middle){
			//完成刚才排序的位置调整
			numbers[k]=helper[i];
			k++;
			i++;
		}
	}
	 
	
}




测试代码:
public class Test01
{
	public static void main(String[] args)
	{
		  int[] numbers={3,1,2,6,7,3,4};
		  
		  
		  Mergesort sorter=new Mergesort();
		  
		  sorter.sort(numbers);
		 
		  for(int i:numbers){
			  System.out.println(i);
		  }
		  //1 2 3 3 4 6 7

	}
}



jdk的各种算法包括binary search,mergesort都在Arrays类里面。
都是加入了泛型的。
都是sun公司的高手写的。 想提高的话可以去研究研究。。

MergeSort Algorithm 归并排序 例子

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
起源:冯·诺依曼最早在EDVAC上实现 基本思想: 将数组一分为(Divide array into two halves) 对每
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
1 归并排序(MergeSort) 归并排序最差运行时间是O(nlogn),它是利用递归设计程序的典型例子。 归并
今天小玩了一会,嘻嘻,的该写点东西了,下午吃饭前复习了一下分治法排序,这个算法是主要思想是分
1, 复杂度:O (n log n) 2路归并排序的基本思想:n个记录,看作n个有序子序列,每个子序列的长度为
  堆是一种完全二叉树结构,并且其满足一种性质:父节点存储值大于(或小于)其孩子节点存储值,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号