插入排序算法優(yōu)化①

汪紅霞，邵飛飛

(安徽新華學(xué)院1.信息工程學(xué)院，2.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230088)

0 引 言

隨著社會的發(fā)展，排序作為一種提高查詢效率的手段顯得越來越重要，尤其是在大數(shù)據(jù)與云計(jì)算廣泛應(yīng)用的今天，大量雜亂無序的信息數(shù)據(jù)，如果不按照一定的規(guī)則排序，會大大降低信息交換工作和查詢的效率，因此對排序算法的研究工作存在著一定的實(shí)用價值［1～4］.本文主要針對插入排序算法進(jìn)行優(yōu)化，研究高效、合適排序算法提升信息交流和查找的效率，減少排序時間.

1 相關(guān)工作

近年來，學(xué)者們就各種排序算法提出了不同程度的優(yōu)化，使排序效率有了不同程度的提升，文獻(xiàn)［5］僅僅對已有的直接插入排序算法進(jìn)行闡述及算法分析.文獻(xiàn)［6］主要分析了插入排序、選擇排序、交換排序，歸并排序、分配排序這幾種排序的思路，比較了它們之間算法性能.文獻(xiàn)［7］主要對直接插入排序、簡單選擇排序進(jìn)行程序設(shè)計(jì)思想、性能指標(biāo)分析.但是這些優(yōu)化過的排序算法適用于小數(shù)組，對于大量雜亂數(shù)據(jù)的排序效率并不高.本文主要針對當(dāng)今社會的龐雜數(shù)據(jù)應(yīng)用排序，就直接插入排序算法提出優(yōu)化思路和改進(jìn)方案，使其在使用計(jì)算機(jī)處理規(guī)模越來越大的數(shù)據(jù)的問題上，能夠更適應(yīng)當(dāng)下技術(shù)的發(fā)展趨勢.

2 排序算法的優(yōu)化過程

為了能夠通過減少交換和比較次數(shù)來減少排序時間，本文就插入排序采用隨機(jī)選取無序區(qū)元素、分組、增量、設(shè)立標(biāo)志位等方法進(jìn)行優(yōu)化.

2.1 插入排序的優(yōu)化

直接插入排序法的過程是每次取無序區(qū)的第一個元素插入有序區(qū).對排列完全逆序的數(shù)組來說，這樣固定的選取元素執(zhí)行插入操作效率非常低.因此，需采用一些策略進(jìn)行優(yōu)化.

2.2.1 隨機(jī)獲取無序區(qū)元素

使用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生無序區(qū)一個數(shù)組的下標(biāo)，如果這個數(shù)值小于無序區(qū)的第一個數(shù)，則交換這兩個數(shù)，然后按照插入排序?qū)o序區(qū)的第一個數(shù)插入到有序區(qū).部分代碼如下:

2.2.2 分成兩組

在2.2.1 中，對無序區(qū)采用隨機(jī)數(shù)產(chǎn)生器來獲取一個未知大小的數(shù)的位置，避免了數(shù)組中大量降序排列帶來的大量移動.但僅這樣做是無法使效率提高到令人滿意的水平的，因此在2.2.1 的基礎(chǔ)上采用分組策略，即將數(shù)組分成兩組進(jìn)行插入排序，然后進(jìn)行整體插入排序，以達(dá)到減少比較移動次數(shù)的目的.部分代碼如下:

將數(shù)組劃分為兩組再進(jìn)行插入排序，排序效率提升的幅度不大，故采取多分組的策略對整個數(shù)組進(jìn)行劃分.根據(jù)測試，當(dāng)步長為976 時，分組效果最好.因此我們按照976 步長將數(shù)組分成若干組，分別對每組進(jìn)行插入排序，最后再進(jìn)行一趟插入排序.優(yōu)化后簡略代碼如下:

圖1 插入排序優(yōu)化前后的對比

2.2.3 增量策略

增量分組的策略能滿足數(shù)據(jù)量大情況下的排序要求，但這種策略對步長的要求很嚴(yán)格，經(jīng)過測試，步長最高限定在31250 左右為佳.因此采讓步長在31250 的限度下依次遞減，每個數(shù)組的長度依次增加.簡略代碼如下:

2.2.4 設(shè)立標(biāo)志位

這種方法的優(yōu)化思想是:設(shè)立一個標(biāo)志位，標(biāo)志位用來判斷本次快速排序是否產(chǎn)生元素交換，如果沒有產(chǎn)生元素交換，即當(dāng)每個分組都有序時，直接跳出循環(huán).當(dāng)每個分組都有序時，直接跳出循環(huán).

在數(shù)組基本有序的情況下，不必要的比較會產(chǎn)生時間上的消耗，因此設(shè)立一個標(biāo)志位，若本次循環(huán)沒有發(fā)生交換，說明上次循環(huán)后，數(shù)組已經(jīng)有序，就跳出循環(huán)，進(jìn)行最后一趟插入排序，簡明代碼如下:

……//最后再進(jìn)行一趟插入排序

2.2.5 實(shí)驗(yàn)結(jié)果

直接插入排序在一種有序數(shù)組上的排序效率很高，可以達(dá)到10 毫秒以內(nèi)，而在相反序列的數(shù)組上排序效率卻很低，在40 萬毫秒級左右，由圖1 優(yōu)化前后對比圖可以看出，升序數(shù)組和降序數(shù)組的排序時間都穩(wěn)定在100 毫秒以內(nèi);對于隨機(jī)數(shù)組和重復(fù)數(shù)組，優(yōu)化后的插入排序也能夠很快將其排列有序，達(dá)到了優(yōu)化前的目標(biāo).但分組策略，使得插入排序算法變得不穩(wěn)定，這也是算法的缺點(diǎn)，還有待改進(jìn).

3 結(jié)束語

總之，針對在大數(shù)據(jù)和云計(jì)算的應(yīng)用，本文在直接插入排序算法過程中，采用遞歸的思想，把大問題分解為小問題，對小數(shù)組加以分析針對不同的特點(diǎn)采用不同的優(yōu)化策略.實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的算法在隨機(jī)數(shù)組、升序數(shù)組、降序數(shù)組和重復(fù)數(shù)組上的排序比較和移動交換次數(shù)，大大縮短了排序時間，提高了排序效率.

［1］ 常璐，夏祖奇.搜索引擎的幾種常用排序算法［J］.圖書情報工作，2003(6):70－73.

［2］ 張曉剛，李明樹.智能搜索引擎技術(shù)的研究與發(fā)展［J］.計(jì)算機(jī)工程與應(yīng)用，2001，37(24):67－70.

［3］ 王曉東.計(jì)算機(jī)算法分析與設(shè)計(jì)［M］.北京:電子工業(yè)出版社，2009:12－61.

［4］ 于俊超.排序算法在生活中的應(yīng)用［J］.北京電力高等?？茖W(xué)校學(xué)報(自然科學(xué)版)，2010，27(6):113－113.

［5］ 李晶.直接插入排序算法分析與實(shí)現(xiàn)［J］.中國科技信息，2007(12):347－349.

［6］ 嚴(yán)瑋.各種常用排序算法的分析與比較［J］.軟件導(dǎo)刊(教育技術(shù))，2013(3):72－74.

［7］ 吳紅芝，郭麥成，吳浩.數(shù)據(jù)結(jié)構(gòu)中內(nèi)部排序算法的分析［J］.計(jì)算機(jī)時代，2010(6):38－39.