用JAVA语言改进插入排序算法

维普资讯 http://www.cqvip.com ８４　第１２期ＮＯ．１２　宜宾学院学报Ｊｏｕｒｎａｌ　ｏｆ　Ｙｉｂｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　用ＪＡＶＡ语言改进插人排序算法　季忠苑　（浙江丽水学院计算机系，浙江丽水３２３０００）　摘要：在很多排序操作中，我们都套用剐插入排序算－击。为了提高插入排序算＿击的性能，文章着重介绍了用ＪＡｖＡ语言编写的改进后的插入排序算　关键词：ＪＡＶＡ；插入排序；快速排序　中圈分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７１—５３６５（２００６）１２－００８４—０２　０引言　ｉｆ（Ａ［ｉ］．ｃｏｍｐａｒｅＴｏ（Ｓｅｎｔｉｎｅｌ—ｖｌａｕｅ）（Ｏ）　很多算法都涉及查找操作，往往查找需要进行两类不同的　Ｓｅｎｔｉｎｅｌ—ｖｌａｕｅ＝Ａ［Ｓｅｎｔｉｎｅｌ—ｐｏｓｔｉｏｎ＝Ｉ］．　测试：一类用于测试是否找到待查找元素，另一类测试则用于判　插入排序往往用于快速排序的最后阶段。若是这样的话，插　断查找是否还在指定的数据结构范围内。实际上，这两类测试可　人排序可用于部分有序的数组中，并且我们可知“监视哨”必将　通过所谓的“监视哨”合二为一的。特别是，“监视哨”可用于插　在数组的最小的Ｋ个元素中（这里的Ｋ是某个依赖实现的常数，　人排序算法中，以使算法的执行效率更高，甚至还能使循环内的　典型的是１６左右的数，往往要远小于Ａ．１ｅｎｔｇｈ的值（也就是数　比较次数减少一半。因为“监视哨”对于插入排序来说，它是一　组的长度）。作为快速排序的使用，代码还需要重写以便与实际　个内部元素，所以在线性时间内就可找到并插入到指定位置上，　相符，使第一步所花费的时间可大大改善（时间复杂度为０（Ａ．　并且这个操作在整个算法中仅仅需要做一次。　１ｅｎｇｔｈ／Ｋ））。　基于这种思想，本文给出了对一个给定的数组进行升序排　１．２在指定的位置插入“监视哨”　序的ＪＡＶＡ代码。代码所涉及的算法对于稳定和不稳定排序均　基于稳定或不稳定排序的不同需要，对应的设置“监视哨”　适用。当然，不稳定排序要更高效些。　有两种不同的方法。　・　改进后的插人排序算法对数组Ａ排序分三步：查找“监视　对于更高效的不稳定排序（在待排序的记录中若有多个相　哨”，插人到指定的数组位置上（在Ａ［Ｏ］处）；最后对数组Ａ的剩　同的关键字，在用某种方法排序之后，这些关键字相同的记录相　余元素进行高效率的插入排序。值得注意的是：在ＪＡＶＡ中数组　对先后次序会发生变化的）设置“监视哨”可用以下两条语句实　Ａ的下标是从０到Ａ．１ｅｎｇｔｈ一１间变化的。尽管利用该算法可对　现：　整型或一些其它简单类型的数组进行直接有效的排序，但这里　／／不稳定排序　为了使算法更通用，我们借助了ＪＡＶＡ的Ｃｏｍｐａｒａｂｌｅ接口：也就　Ａ［ｅＳｎｔｉｎｅｌ—ｐｏｓｔｉｏｎ］＝Ａ［０］；　是说，算法可对任何支持Ｃｏｍｐａｒａｂｌｅ接口的类进行排序。　Ａ［０］＝Ｓｅｎｔｉｎｅ１．ｖａｌｕｅ；　１算法实现　对于稳定排序（在待排序的记录中若有多个相同的关键字，　算法的具体步骤如下：　在用某种方法排序之后，这些关键字相同的记录相对先后次序　１．１获取“监视哨”的位置和大小　不变的），我们可通过先对所有数组下标介于０到Ｓｅｎｔｉｎｅｌ—ｐｏｓ・　／／Ｓｅｎｔｉｎｅｌ—ｐｏｓｉｔｉｏｎ，Ｓｅｎｔｉｎｅｌ—ｖａｌｕｅ分别为“监视哨”的位置和　ｔｉｏｎ一１的数组元素后移一位，而后把“监视哨”放在Ａ［０］上：　值变量。　／／稳定排序　ｉｎｔ　ｅＳｎｔｉｎｅｌ—ｐｏｓｉｔｉｏｎ＝０；　ｆ０ｒ（ｉｎｌ　ｉ—Ｓｅｎｔｉｎｅｌ　ｐｏｓｉｔｉｏｎ；ｉ＞Ｏ；ｉ一一）　Ｃｏｍｐａｒａｂｌｅ　Ｓｅｎｔｉｎｅｌ—ｖａｌｕｅ＝Ａ［Ｓｅｎｔｉｎｅｌ—ｐｏｓｉｔｉｏｎ］；　Ａ［ｉ］＝Ａ［ｉ一１］；　ｆ０ｒ（ｉｎｌ　ｉ＝１；ｉ＜ａ．１ｅｎｇｔｈ；ｉ＋＋）　Ａ［０］＝Ｓｅｎｔｉｎｅｌ—ｖａｌｕｅ；　收稿日期：２００６～０８—２２　作者简介：季忠苑（１９７５一）、男，软件设计师，讲师，主要从事软件工程研究　维普资讯 http://www.cqvip.com ２００６年１２月　季忠苑：用ｊＡＶＡ语言改进插入排序算法　８５　１．３剩余数组元素的插入排序　｝　到目前为止，Ａ［Ｏ］就是数组Ａ的最小元素（即“监视哨”），　那么算法的下一步：　插入算法本身，就可以：（１）避免内层循环中的边界检验，因　｝　Ａ［ｊ］＝Ｖ；　２总结　为指定的待插入值Ｖ肯定在给定的范围内的；（２）外层循环也可　通过引入“监视哨”，优化了传统的插入排序算法，使比较次　从而提高了整个算法的时间效率。　从－＿２开始，因为Ａ［Ｏ］是值最小的元素，那么Ａ［０］一定小于Ａ　数大大的减少，［１］，也就是说Ａ［０］，Ａ［１］已经按要求排好序了。　最后一步操作是稳定的操作，整个算法的稳定性取决于第　二步。　ｆ０ｒ（ｊｎｔ　ｊ＝２；ｉ＜Ａ．１ｅｎｇｔｈ；ｉ＋＋）　｛ｉｎｔｊ＝ｉ；　Ｃｏｍｐａｒａｂｌｅ　Ｖ＝Ａ［＿ｉ］；　ｗｈｉｌｅ（Ａ［ｊ－１］．ｃｏｍｐａｒｅＴｏ（Ｖ）＞Ｏ）　｛Ａ［ｊ］＝Ａ［ｊ＿１］；　；一一：　参考文献：　［１）严蔚敏，等．数据结构［Ｍ］．北京：清华大学出版社，１９９７．　［２］王晓东．计算机算法设计与分析（第２版）［Ｍ］．北京：电子工业　出版社，２００５．　［３］王克宏编译．ＪＡＶＡ语言与ＳＱＩ　接１３［Ｍ］．北京：清华大学出版　社，１９９７．４．　［４）张军．电脑家园Ａｕｔｈｏｒｗａｒｅ制作多媒体［Ｊ】．南昌职业技术学院学　报，２００３。（６）．　［５］谢光明．中国电脑教育报，２０００．