首先介绍归并和插入的算法思想,其实现细节可以参考博客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)
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
编程实现 快速排序,堆排序,归并排序,插入排序,选择排序; 对于不同的数组大小,比较这些算法的复杂度; 数组的测试,分为已排序数组和随机数组。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
插入排序、冒泡排序、归并排序、快速排序四种排序方式的C++实现,各写成了一个函数,主函数中可以选择调用那一个。初始化数组时用的是随机种子srand((int)time(0))。在宏中定义数组大小。
归并排序,插入排序,以及两种排序算法的结合C++实现
C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
选择排序,冒泡排序,插入排序 基数排序,快速排序,归并排序
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
给初学者学习算法用,用java实现的排序算法,包括二路归并和插入排序。
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
其中包含了各种对数组排序的方法,数组下标从1开始,有插入排序(直接插入排序、希尔排序),交换排序(起泡排序、快速排序),选择排序(简单选择排序,堆排序(另外写))、归并排序(递归,非递归)。