mergesort.java

java 实现常用数据结构（链表

/*
 * MergeSort.
 * @Author: zhengbotai.
 * @Date: 2007.5
*/
package dreamer.util;
import static java.lang.System.out;
public class MergeSort
{
	public static void merge(int[]a,int first,int mid,int last)
	{
		int len1 = mid-first+1;
		int len2 = last-mid;
		
		int[]tmp = new int[len1+len2];
		
		int index1 = first;
		int index2 = mid+1;
		int m = 0;
		
		while(index1<=mid && index2<=last)
		{
			if(a[index1]<a[index2]) // 1 6 0 -- 3 5 4
			{
				tmp[m] = a[index1];
				m++;
				index1++;
			}
			else
			{
				tmp[m] = a[index2];
				m++;
				index2++;
			}
		}
		while(index1<=mid)
		{
			tmp[m] = a[index1];
			m++;
			index1++;
		}
		while(index2<=last)
		{
			tmp[m] = a[index2];
			m++;
			index2++;
		}
		int t = 0;
	    for(int i=first;i<=last;i++) // merge the part arrays.
	    {
	    	a[i] = tmp[t];
	    	t++;
	    }
	}
	
	public static void mergeSort(int[]a,int first,int last)
	{
		if (first + 1 < last)
        {
            int mid = (first + last) / 2;
            mergeSort(a, first, mid);
            mergeSort(a, mid+1, last);
            merge(a, first, mid, last);
        }
	}
	
	public static void main(String []args)
	{
		int [] a = {1,6,0,3,5,4};
		mergeSort(a,0,5);
	    for(int i:a)
		{
			out.print(i+" ");
		}
	}
}