大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第七章：排序-第二節(jié)-插入排序

第二節(jié)插入排序插入排序(InsertionSort)的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。插入排序主要包括：直接插入排序和希爾排序。當(dāng)前講授一、直接插入排序1、排序思想假設(shè)待排序的記錄存放在數(shù)組R[1..n]中，初始時(shí)，R[1]自成1個(gè)有序區(qū)，無(wú)序區(qū)為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當(dāng)前的有序區(qū)R[1..i-1]中，生成含n個(gè)記錄的有序區(qū)。2、實(shí)例分析【例】給定一組關(guān)鍵字(46，39，17，23，28，55，18，46)，要求按直接插入排序算法給出每一趟排序結(jié)果。3、算法描述voidInsertSort(SeqlistR，intn){//對(duì)順序表R做直接插入排序inti，j；for(i=2；i<=n；i++)if(R[i].key<R[i-1].key)//若R[i].key<R[i]，移動(dòng){R[0]=R[i]；//當(dāng)前記錄復(fù)制為哨兵for(j=i-1；R[0].Key<R[j].key；j--)//找插入位置R[j+1]=R[j]；//記錄后移R[j+1]=R[0]；//R[i]插入到正確位置｝｝4、算法分析（1）哨兵的作用算法中引進(jìn)的附加記錄R[0]稱(chēng)為哨兵(Sentinel)，哨兵有兩個(gè)作用：①進(jìn)入查找(插入位置)循環(huán)之前，它保存了R[i]的副本，不致于因記錄后移而丟失R[i]的內(nèi)容；②它的主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。一旦越界(即j=0)，因?yàn)镽[0].key和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測(cè)j是否越界(即省略了循環(huán)判定條件"j>=1")，使得測(cè)試查找循環(huán)條件的時(shí)間大約減少了一半。（2）算法的時(shí)間性能分析對(duì)于具有n個(gè)記錄的文件，要進(jìn)行n-1趟排序。各種狀態(tài)下的時(shí)間復(fù)雜度：（3）算法的空間復(fù)雜度分析算法所需的輔助空間是一個(gè)監(jiān)視哨，輔助空間復(fù)雜度S(n)=O(1)。是一個(gè)就地排序。（4）直接插入排序是穩(wěn)定的排序方法。二、希爾排序1、排序思想先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入方法。2、實(shí)例分析初始關(guān)鍵字序列為(36，25，48，27，65，25，43，58，76，32)。其增量序列的取值依次為5，3，l，排序過(guò)程如圖所示。3、算法描述voidShellInsert(SeqlistR，intdk，intn){//希爾排序中的一趟插入排序，dk為當(dāng)前增量inti，j；for(i=dk+1；i<=n；i++)//將R[dk+1…n]分別插入有序區(qū)if（R[i].key<R[i-dk].key）{R[0]=R[i]；//暫存在R[0]中j=i-dk；while(j>0&&R[0].key<R[j].key){R[j+dk]=R[j]；//記錄后移，查找插入位置j=j-dk；//查找前一記錄}R[j+dk]=R[0];//插入R[i]到正確位置}}voidshellsort(seqListR，intd[]，intt，intn){//按增量序列d[0…t-1]對(duì)順序表R作希爾排序intk；for(k=0；k<t；k++)ShellInsert(R，d[k]，n)；}4、算法分析（1）增量序列的選擇①最后一個(gè)增量必須為1；②應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。（2）Shell排序的時(shí)間性能優(yōu)于直接插入