大范围归并小范围插入排序

首先介绍归并和插入的算法思想，其实现细节可以参考博客http://java--hhf.iteye.com/blog/2034925/，然后再具体实现本文主要介绍的“大范围归并小范围插入排序”

（一）插入排序

算法执行思路如图

 实现算法：


 

（二）归并排序（分治法）

先将源数据分成一个一个的小组，然后两两合并即是

 

合并两个数据的实现思路：（将L,R合并为A返回）


时间复杂度

（三）

/**
 * 先插入排序再归并
 * 时间复杂度 nk+nlg(kn)
 * @author HHF
 * 2014年11月24日
 */
public class MergeInsert {
        private static final int k = 1000;
	public static void main(String[] args) {
		int[] array = Common.random(0,10000,1000);
		System.out.print("原始数据：");
		Common.printIntoTxt(array);
		sort(array1, 0, array1.length-1);;
		System.out.print("结果数据：");
		Common.printIntoTxt(array);
	}
	
	public static void sort(int[] array, int start, int end) {
		if(start+k < end){//已经递归到了最后 每个集合里面*一个元素
			int middle = (end+start)/2;
			sort(array, start, middle);
			sort(array, middle+1, end);
			merge(array, start, middle, end);
		}else{
			insert(array, start, end);
		}
	}
	/**
	 * 插入排序
	 * @param array
	 * @param end 
	 * @param start 
	 */
	public static void insert(int[] array, int start, int end){
		//从第二个开始 往上找下标比它小的数进行比较
		int size = end-start+1;
		for(int i=1; i<size; i++){
			for(int j=i-1; j>=0; j--){
				if(array[start+j+1]<array[start+j]){//找到了i的正确位置 为j+1
					Common.swap(array, start+j+1, start+j);
				}
			}
			//Common.print(array);
		}
	}
	/**
	 * 将两个数组合并
	 * @param array
	 * @param array2
	 * @return 是否成功合并
	 */
	private static Boolean merge(int[] array, int start, int middle, int end) {
		int size1 = middle - start + 1;//[start, middle]
		int size2 = end - middle;//(middle, end]
		int[] array1 = new int[size1];
		int[] array2 = new int[size2];
		int i=0, j=0, k=start;
		while(i<size1){//获取到array数组左边的值
			array1[i] = array[start+i];
			i++;
		}
		while(j<size2){//获取到array数组右边的值
			array2[j] = array[middle+1+j];
			j++;
		}
		i=j=0;
		while(i<size1 && j<size2){//将两者中数据插入到新的数组中去
			if(array1[i]<array2[j]){
				array[k++] = array1[i];
				i++;
			}else{
				array[k++] = array2[j];
				j++;
			}
		}
		//收拾还剩余的数据
		if(i<size1){
			while(i<size1){
				array[k++] = array1[i];
				i++;
			}
		}
		if(j<size2){
			while(j<size2){
				array[k++] = array2[j];
				j++;
			}
		}
		array1 = null;
		array2 = null;
		if(k == end+1){
			return true;
		}else{
			return false;
		}
	}	
}

 
 （四）内排序下界

 堆排序具体实现可以参考博客http://java--hhf.iteye.com/blog/2034925/

(ps:附件内附上工具类Common.zip)