插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。
??? 本節介紹兩種插入排序方法：直接插入排序和希爾排序。
直接插入排序基本思想
1、基本思想
??? 假設待排序的記錄存放在數組R[1..n]中。初始時，R[1]自成1個有序區，無序區為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當前的有序區R[1..i-1]中，生成含n個記錄的有序區。
2、第i-1趟直接插入排序：
??? 通常將一個記錄R[i](i=2，3，…，n-1)插入到當前的有序區，使得插入后仍保證該區間里的記錄是按關鍵字有序的操作稱第i-1趟直接插入排序。
??? 排序過程的某一中間時刻，R被劃分成兩個子區間R[1．．i-1]（已排好序的有序區）和R[i．．n]（當前未排序的部分，可稱無序區）。
??? 直接插入排序的基本操作是將當前無序區的第1個記錄R[i]插人到有序區R[1．．i-1]中適當的位置上，使R[1．．i]變為新的有序區。因為這種方法每次使有序區增加1個記錄，通常稱增量法。
??? 插入排序與打撲克時整理手上的牌非常類似。摸來的第1張牌無須整理，此后每次從桌上的牌(無序區)中摸最上面的1張并插入左手的牌(有序區)中正確的位置上。為了找到這個正確的位置，須自左向右(或自右向左)將摸來的牌與左手中已有的牌逐一比較。
一趟直接插入排序方法
1．簡單方法
??? 首先在當前有序區R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然后將R[k．．i-1]中的記錄均后移一個位置，騰出k位置上的空間插入R[i]。
? 注意：
??? 若R[i]的關鍵字大于等于R[1．．i-1]中所有記錄的關鍵字，則R[i]就是插入原位置。
2．改進的方法
一種查找比較操作和記錄移動操作交替地進行的方法。
具體做法：
??? 將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：
??? ① 若R[j]的關鍵字大于R[i]的關鍵字，則將R[j]后移一個位置；
??????②若R[j]的關鍵字小于或等于R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。
??? 關鍵字比R[i]的關鍵字大的記錄均已后移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。
直接插入排序算法
1．算法描述
? void lnsertSort(SeqList R)
?? { //對順序表R中的記錄R[1..n]按遞增序進行插入排序
??? int i，j；
??? for(i=2;i<=n；i++) //依次插入R[2]，…，R[n]
????? if(R[i].key<R[i-1].key){//若R[i].key大于等于有序區中所有的keys，則R[i]
????????????????????????????? //應在原有位置上
??????? R[0]=R[i];j=i-1; //R[0]是哨兵，且是R[i]的副本
??????? do{ //從右向左在有序區R[1．．i-1]中查找R[i]的插入位置
???????? R[j+1]=R[j]； //將關鍵字大于R[i].key的記錄后移
???????? j-- ；
???????? }while(R[0].key<R[j].key)； //當R[i].key≥R[j].key時終止
??????? R[j+1]=R[0]； //R[i]插入到正確的位置上
?????? }//endif
?? }//InsertSort
2．哨兵的作用
??? 算法中引進的附加記錄R[0]稱監視哨或哨兵(Sentinel)。
??? 哨兵有兩個作用：
① 進人查找(插入位置)循環之前，它保存了R[i]的副本，使不致于因記錄后移而丟失R[i]的內容；
② 它的主要作用是：在查找循環中"監視"下標變量j是否越界。一旦越界(即j=0)，因為R[0].key和自己比較，循環判定條件不成立使得查找循環結束，從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件"j>=1")。
? 注意：
? ① 實際上，一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵。
? 【例】單鏈表中的頭結點實際上是一個哨兵
② 引入哨兵后使得測試查找循環條件的時間大約減少了一半，所以對于記錄數較大的文件節約的時間就相當可觀。對于類似于排序這樣使用頻率非常高的算法，要盡可能地減少其運行時間。所以不能把上述算法中的哨兵視為雕蟲小技，而應該深刻理解并掌握這種技巧。
給定輸入實例的排序過程
??? 設待排序的文件有8個記錄，其關鍵字分別為：49，38，65，97，76，13，27，49。為了區別兩個相同的關鍵字49，后一個49的下方加了一下劃線以示區別。其排序過程見【
動畫模擬演示
】
算法分析
1．算法的時間性能分析?
??? 對于具有n個記錄的文件，要進行n-1趟排序。
??? 各種狀態下的時間復雜度：
┌─────────┬─────┬──────┬──────┐
│ 初始文件狀態???? │?? 正序?? │???? 反序?? │無序(平均)? │
├─────────┼─────┼──────┼──────┤
│ 第i趟的關鍵????? │?? 1????? │???? i+1??? │ （i-2）/2? │
│ 字比較次數?????? │????????? │??????????? │??????????? │
├─────────┼─────┼──────┼──────┤
│總關鍵字比較次數? │?? n-1??? │(n+2)(n-1)/2│ ≈n2/4???? │
├─────────┼─────┼──────┼──────┤
│第i趟記錄移動次數 │?? 0????? │ i+2??????? │ （i-2）/2? │
├─────────┼─────┼──────┼──────┤
│總的記錄移動次數? │?? 0????? │(n-1)(n+4)/2│ ≈n2/4???? │
├─────────┼─────┼──────┼──────┤
│時間復雜度??????? │? 0（n）? │ O（n2）??? │ O（n2）??? │
└─────────┴─────┴──────┴──────┘
注意：
??? 初始文件按關鍵字遞增有序，簡稱"正序"。
??? 初始文件按關鍵字遞減有序，簡稱"反序"。
2．算法的空間復雜度分析
??? 算法所需的輔助空間是一個監視哨，輔助空間復雜度S(n)=O(1)。是一個就地排序。
|
??? 希爾排序(Shell Sort)是插入排序的一種。因D．L．Shell于1959年提出而得名。
希爾排序基本思想
? 基本思想：
??? 先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
??? 該方法實質上是一種分組插入方法。
給定實例的shell排序的排序過程
??? 假設待排序文件有10個記錄，其關鍵字分別是：
??????? 49，38，65，97，76，13，27，49，55，04。
??? 增量序列的取值依次為：
??????? 5，3，1
??? 排序過程如【
動畫模擬演示
】。
Shell排序的算法實現
1． 不設監視哨的算法描述
? void ShellPass(SeqList R，int d)
?? {//希爾排序中的一趟排序，d為當前增量
???? for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區
?????? if(R[i].key<R[i-d].key){
???????? R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵
???????? do {//查找R[i]的插入位置
??????????? R[j+d]；=R[j]； //后移記錄
??????????? j=j-d； //查找前一記錄
???????? }while(j>0&&R[0].key<R[j].key)；
???????? R[j+d]=R[0]； //插入R[i]到正確的位置上
?????? } //endif
?? } //ShellPass
? void? ShellSort(SeqList R)
?? {
??? int increment=n； //增量初值，不妨設n>0
??? do {
????????? increment=increment/3+1； //求下一增量
????????? ShellPass(R，increment)； //一趟增量為increment的Shell插入排序
?????? }while(increment>1)
??? } //ShellSort
? 注意：
??? 當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內循環中增加了一個循環判定條件"j>0"，以防下標越界。
2．設監視哨的shell排序算法
??? 具體算法【參考書目[12] 】
算法分析
1．增量序列的選擇
??? Shell排序的執行時間依賴于增量序列。
??? 好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
??? 有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。
2．Shell排序的時間性能優于直接插入排序
??? 希爾排序的時間性能優于直接插入排序的原因：
①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。
③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。
??? 因此，希爾排序在效率上較直接插人排序有較大的改進。
3．穩定性
??? 希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發生了變化。
|
3．直接插入排序的穩定性
??? 直接插入排序是穩定的排序方法。