- 浏览: 303293 次
- 性别:
- 来自: 郴州
文章分类
- 全部博客 (70)
- hadoop (0)
- lucene (1)
- heritrix (1)
- webservice (0)
- css+div (0)
- java (29)
- javaweb (3)
- spring (2)
- hibernate (3)
- struts (5)
- struts2 (3)
- tomcat (1)
- map/reduce (0)
- ajax (0)
- android (3)
- oracle (3)
- 面试题 (1)
- 生活 (0)
- 开发工具 (1)
- 面试实习 (0)
- 设计模式 (3)
- 数据结构 (5)
- 论坛 (2)
- flex (3)
- PureMVC (1)
- java,jdk (1)
- sql server (1)
- 报表 (1)
- 算法 (4)
- 工作 (0)
最新评论
-
lp895876294:
第三种方式类似于工厂方法模式了
设计模式之单例模式(三种实现方式) -
xchsh12345:
如果用的是linux服务器呢
解决利用iText导出PDF报表中文乱码两种方式 -
memoryisking:
写的不错,关于Timer和TimeTask的内容网上资料挺多的 ...
Java定时调度 Timer类和TimerTask类 -
linfeng0169:
写的不错~!不过就是解释的不算好!
Calendar类add()与roll()方法的区别 -
u013606853:
好流弊的样子,LZ V5~
hibernate注解详解
插入排序主要包括直接插入排序、shell排序和折半插入等几种排序。这篇文章主要说明直接插入排序、shell排序和折半插入三种排序的java实现。
一、直接插入排序
直接插入排序(straight insertion sort)的作法是:
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。
二、折半插入排序
折半插入排序的基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法寻找V[i]的插入位置。
三、shell排序
希尔排序基本思想
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
算法步骤
Step1 将n个元素个数列分为5个小组,在每个小组内按直接插入法排序;
step2 在第i步,分组个数取 di+1 =(di +1)/2 {9,5,3,2,1};相临两组之间的对应元素进行比较,如果ai>aj,则交换它们的位置;
Step3 当dK = 1的循环过程完成后,排序过程结束。
Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
稳定性
希尔排序是不稳定的。
一、直接插入排序
直接插入排序(straight insertion sort)的作法是:
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序,时间复杂性为o(n^2),空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。
//定义一个数据包装类 public class DataWrap implements Comparable<DataWrap> { int data; String flag; public DataWrap(int data, String flag) { this.data = data; this.flag = flag; } public String toString() { return data + flag; } //根据data实例变量来决定两个DataWrap的大小 public int compareTo(DataWrap dw) { return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1); } }
public class InsertSort { public static void insertSort(DataWrap[] data) { System.out.println("开始排序:\n"); int arrayLength = data.length; for (int i = 1 ; i < arrayLength ; i++ ) { //当整体后移时,保证data[i]的值不会丢失 DataWrap tmp = data[i]; //i索引处的值已经比前面所有值都大,表明已经有序,无需插入 //(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值) if (data[i].compareTo(data[i - 1]) < 0) { int j = i - 1; //整体后移一格 for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j--) { data[j + 1] = data[j]; } //最后将tmp的值插入合适位置 data[j + 1] = tmp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9 , ""), new DataWrap(-16 , ""), new DataWrap(21 , "*"), new DataWrap(23 , ""), new DataWrap(-30 , ""), new DataWrap(-49 , ""), new DataWrap(21 , ""), new DataWrap(30 , "*"), new DataWrap(30 , "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); insertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
二、折半插入排序
折半插入排序的基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法寻找V[i]的插入位置。
public class BinaryInsertSort { public static void binaryInsertSort(DataWrap[] data) { System.out.println("开始排序:\n"); int arrayLength = data.length; for(int i = 1 ; i < arrayLength ; i++) { //当整体后移时,保证data[i]的值不会丢失 DataWrap tmp = data[i]; int low = 0; int high = i - 1; while(low <= high) { //找出low、high中间的索引 int mid = (low + high) / 2; //如果tmp值大于low、high中间元素的值 if(tmp.compareTo(data[mid]) > 0) { //限制在索引大于mid的那一半中搜索 low = mid + 1; } else { //限制在索引小于mid的那一半中搜索 high = mid - 1; } } //将low到i处的所有元素向后整体移一位 for(int j = i ; j > low ; j--) { data[j] = data[j - 1]; } //最后将tmp的值插入合适位置 data[low] = tmp; System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9 , ""), new DataWrap(-16 , ""), new DataWrap(21 , "*"), new DataWrap(23 , ""), new DataWrap(-30 , ""), new DataWrap(-49 , ""), new DataWrap(21 , ""), new DataWrap(30 , "*"), new DataWrap(30 , "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); binaryInsertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
三、shell排序
希尔排序基本思想
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
算法步骤
Step1 将n个元素个数列分为5个小组,在每个小组内按直接插入法排序;
step2 在第i步,分组个数取 di+1 =(di +1)/2 {9,5,3,2,1};相临两组之间的对应元素进行比较,如果ai>aj,则交换它们的位置;
Step3 当dK = 1的循环过程完成后,排序过程结束。
Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
稳定性
希尔排序是不稳定的。
public class ShellSort { public static void shellSort(DataWrap[] data) { System.out.println("开始排序:"); int arrayLength = data.length; //h变量保存可变增量 int h = 1; //按h * 3 + 1得到增量序列的最大值 while(h <= arrayLength / 3) { h = h * 3 + 1; } while(h > 0) { System.out.println("===h的值:" + h + "==="); for (int i = h ; i < arrayLength ; i++ ) { //当整体后移时,保证data[i]的值不会丢失 DataWrap tmp = data[i]; //i索引处的值已经比前面所有值都大,表明已经有序,无需插入 //(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值) if (data[i].compareTo(data[i - h]) < 0) { int j = i - h; //整体后移h格 for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j-=h) { data[j + h] = data[j]; } //最后将tmp的值插入合适位置 data[j + h] = tmp; } System.out.println(java.util.Arrays.toString(data)); } h = (h - 1) / 3; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9 , ""), new DataWrap(-16 , ""), new DataWrap(21 , "*"), new DataWrap(23 , ""), new DataWrap(-30 , ""), new DataWrap(-49 , ""), new DataWrap(21 , ""), new DataWrap(30 , "*"), new DataWrap(30 , ""), }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); shellSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
发表评论
-
利用微软翻译API替代被停用谷歌翻译API
2012-02-13 13:37 10334众所周知,谷歌已经不支持翻译API1版本了,现在提供了A ... -
(转)Java回调实现
2011-12-08 14:38 1128Java回调实现 轮询:过10分钟就到女朋友宿舍前面去看她有 ... -
java实现排序算法之交换排序(冒泡排序、快速排序)
2011-09-14 21:28 2588交换排序的主体操作是对数组中的数据不断进行交换操作。交换排序主 ... -
java实现排序算法之选择排序(直接选择排序、堆排序)
2011-09-14 20:44 2629常用的选择排序算法有两种:直接选择排序和堆排序。 一、直接选择 ... -
java 实现数据结构之队列
2011-09-14 15:27 12599队列是一种特殊的线性表,它只允许在表的前端(front)进行删 ... -
java 实现数据结构之线性表
2011-09-14 11:44 10665应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数 ... -
java 实现undo和redo操作链表的一种实现
2011-09-14 10:32 2132今天在iteye论坛逛,发现有这么一道笔试题目:实现一个可以增 ... -
jdbc连接mysql oracle sql server数据库的连接字符串
2011-09-13 10:41 2708jdbc连接mysql oracle sql serv ... -
java 利用label标记退出多重循环
2011-09-10 09:16 12028学过C语言的都知道,有个goto关键字,利用goto关键字可以 ... -
一个小学弟问我的算法问题
2011-09-04 20:08 1627在实验室的本科群中,一个小弟问我一个算法问题。说有1,2, ... -
深入JDK源代码之定时操作Timer类和TimerTask类实现
2011-07-26 14:45 3460Timer类是一种线程设施,可以用来实现某一个时间或某 ... -
(转)Java中对象的深复制(深克隆)和浅复制(浅克隆)
2011-07-25 20:31 11931.浅复制与深复制概念 ⑴浅复制(浅克隆) 被复制对象 ... -
深入JDK源代码之LinkedList类
2011-07-26 09:09 1883public class LinkedList<E> ... -
Java中的transient关键字
2011-07-25 14:36 24882transient说明一个属性是临时的,不会被序列化。 下面是 ... -
深入JDK源代码之Observer接口和Observable类实现观察者模式
2011-07-25 11:46 3407一、何为观察者模式? 观察者模式(有时又被称为发布/ ... -
深入JDK源代码之ArrayList类
2011-07-22 11:19 2909public class ArrayList<E&g ... -
深入JDK源代码之Arrays类中的排序查找算法
2011-07-22 09:58 3941最近在暑假实习, ... -
java 实现数据结构之栈
2011-07-10 21:51 4637在学数据结构课程 ... -
Java定时调度 Timer类和TimerTask类
2011-07-10 15:38 23874Timer类是一种线程设施,可以用来实现某一个时间或某一段 ... -
Calendar类add()与roll()方法的区别
2011-07-06 22:45 10929JDK API中对这两个方法的说明如下: abstract ...
相关推荐
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
做了个Java Swing 图形界面,选择3中排序方法进行排序。工程用NetBeans 打开,运行Main.java文件或直接点击运行主程序,...BinSort.java(折半插入排序) QKSort.java(快速排序算法) SelectSort.java(简单选择排序)
提供五种排序算法的C++实现方法,输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现...
数据结构排序算法中的折半插入排序,又称二分法,是对基本插入排序的一种改进,比普通的插入排序要快
包括常见的排序算法,以及折半查找,首先对要查找的数据排好序,然后用递归调用的方式实现折半查找(包括了两种实现方式)。指定一个排好序的数组和要查找的值,同时指定要查找的左边界和有边界。左右边界要位于数组...
快速排序 希尔排序 插入排序 折半排序算法
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
java 快速排序 折半查找的界面实现 (递归与分治法)
实现折半插入排序以及数据是否有序的判断 还可以判断一个数据是否为堆
随机生成小于5000的数 根据操作通过不同的方法排序 泡泡排序 直接插入排序 折半插入排序 希尔排序 直接选择排序 统计时间 比较次数和交换次数 保存为txt文件
直接插入排序、折半插入排序、希尔排列
直接插入、折半插入、冒泡、快速、简单选择等排序方法 用c语言实现 代码运行正常 不会有任何的问题
用函数实现折半插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 5...
数据结构中的折半插入排序算法用C语言来实现的完整示例程序
含有折半插入、交换冒泡、堆排序、直接插入、归并排序、快速排序、基数排序、简单选择、希尔排序等的算法实现
主要介绍了Java实现直接插入排序和折半插入排序算法示例,文中对算法的思想和时间复杂度都有简单的讲解,需要的朋友可以参考下