首页 / 算法 / 大范围归并小范围插入排序
大范围归并小范围插入排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了大范围归并小范围插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2162字，纯文字阅读大概需要4分钟。
内容图文
首先介绍归并和插入的算法思想，其实现细节可以参考博客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)
原文：http://java--hhf.iteye.com/blog/2163465
内容总结
以上是互联网集市为您收集整理的大范围归并小范围插入排序全部内容，希望文章能够帮你解决大范围归并小范围插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。