欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-25 19:18:17
...

首先介绍归并和插入的算法思想,其实现细节可以参考博客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)

  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 31.3 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 11.4 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 6.3 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 12.2 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 47.8 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 5.7 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 22.4 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 865 Bytes
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 20.9 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 3.7 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 4.2 KB
  • 大范围归并小范围插入排序
            
    
    博客分类: 数据结构 插入排序分治法归并排序堆排序排序 
  • 大小: 3.6 KB