MergeSort Algorithm 归并排序 例子_JAVA_编程开发_程序员俱乐部

摘自 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模式里研究了半天，大概明白了那么一点点。

实现代码：

class="java">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公司的高手写的。 想提高的话可以去研究研究。。