假設(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．第 i-1 趟直接插入排序

通常將一個(gè)記錄 R[i][i=2，3，…，n-1]插入到當(dāng)前的有序區(qū)，使得插入后仍保證該區(qū)間里的記錄是按關(guān)鍵字有序的操作稱第 i-1 趟直接插入排序。

排序過(guò)程的某一中間時(shí)刻，R 被劃分成兩個(gè)子區(qū)間 R[1．．i-1]（已排好序的有序區(qū)）和 R[i．．n]（當(dāng)前未排序的部分，可稱無(wú)序區(qū)）。

直接插入排序的基本操作是將當(dāng)前無(wú)序區(qū)的第 1 個(gè)記錄 R[i]插人到有序區(qū) R[1．．i-1]中適當(dāng)?shù)奈恢蒙?，?R[1．．i]變?yōu)樾碌挠行騾^(qū)。因?yàn)檫@種方法每次使有序區(qū)增加1個(gè)記錄，通常稱增量法。

插入排序與打撲克時(shí)整理手上的牌非常類似。摸來(lái)的第 1 張牌無(wú)須整理，此后每次從桌上的牌(無(wú)序區(qū))中摸最上面的 1 張并插入左手的牌(有序區(qū))中正確的位置上。為了找到這個(gè)正確的位置，須自左向右(或自右向左)將摸來(lái)的牌與左手中已有的牌逐一比較。

一趟直接插入排序方法

1．簡(jiǎn)單方法

首先在當(dāng)前有序區(qū) R[1..i-1]中查找R[i]的正確插入位置 k(1≤k≤i-1)；然后將 R[k．．i-1]中的記錄均后移一個(gè)位置，騰出 k 位置上的空間插入 R[i]。

注意：若 R[i]的關(guān)鍵字大于等于 R[1．．i-1]中所有記錄的關(guān)鍵字，則 R[i]就是插入原位置。

2．改進(jìn)的方法

一種查找比較操作和記錄移動(dòng)操作交替地進(jìn)行的方法。

具體做法：

將待插入記錄 R[i]的關(guān)鍵字從右向左依次與有序區(qū)中記錄 R[j][j=i-1，i-2，…，1]的關(guān)鍵字進(jìn)行比較：

若 R[j]的關(guān)鍵字大于 R[i]的關(guān)鍵字，則將 R[j]后移一個(gè)位置；
若 R[j]的關(guān)鍵字小于或等于 R[i]的關(guān)鍵字，則查找過(guò)程結(jié)束，j+1 即為 R[i]的插入位置。

關(guān)鍵字比 R[i]的關(guān)鍵字大的記錄均已后移，所以 j+1 的位置已經(jīng)騰空，只要將 R[i] 直接插入此位置即可完成一趟直接插入排序。

直接插入排序算法

1．算法描述

void lnsertSort(SeqList R)  
 { //對(duì)順序表R中的記錄R[1..n]按遞增序進(jì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大于等于有序區(qū)中所有的keys，則R[i]  
                            //應(yīng)在原有位置上  
      R[0]=R[i];j=i-1; //R[0]是哨兵，且是R[i]的副本  
      do{ //從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置  
       R[j+1]=R[j]； //將關(guān)鍵字大于R[i].key的記錄后移  
       j-- ；  
       }while(R[0].key<R[j].key)； //當(dāng)R[i].key≥R[j].key時(shí)終止  
      R[j+1]=R[0]； //R[i]插入到正確的位置上  
     }//endif  
 }//InsertSort

2．哨兵的作用

算法中引進(jìn)的附加記錄 R[0]稱監(jiān)視哨或哨兵(Sentinel)。

哨兵有兩個(gè)作用：

進(jìn)入查找(插入位置)循環(huán)之前，它保存了 R[i]的副本，使不致于因記錄后移而丟失 R[i]的內(nèi)容；
它的主要作用是：在查找循環(huán)中"監(jiān)視"下標(biāo)變量j是否越界。一旦越界(即 j=0)，因?yàn)?R[0].key和自己比較，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束，從而避免了在該循環(huán)內(nèi)的每一次均要檢測(cè)j是否越界(即省略了循環(huán)判定條件"j>=1")。

注意：

實(shí)際上，一切為簡(jiǎn)化邊界條件而引入的附加結(jié)點(diǎn)(元素)均可稱為哨兵。

【例】單鏈表中的頭結(jié)點(diǎn)實(shí)際上是一個(gè)哨兵

引入哨兵后使得測(cè)試查找循環(huán)條件的時(shí)間大約減少了一半，所以對(duì)于記錄數(shù)較大的文件節(jié)約的時(shí)間就相當(dāng)可觀。對(duì)于類似于排序這樣使用頻率非常高的算法，要盡可能地減少其運(yùn)行時(shí)間。所以不能把上述算法中的哨兵視為雕蟲小技，而應(yīng)該深刻理解并掌握這種技巧。

給定輸入實(shí)例的排序過(guò)程

設(shè)待排序的文件有8個(gè)記錄，其關(guān)鍵字分別為：49，38，65，97，76，13，27，49。為了區(qū)別兩個(gè)相同的關(guān)鍵字49，后一個(gè)49的下方加了一下劃線以示區(qū)別。其排序過(guò)程見(jiàn)【動(dòng)畫模擬演示】。

算法分析

1．算法的時(shí)間性能分析

對(duì)于具有 n 個(gè)記錄的文件，要進(jìn)行 n-1 趟排序。

各種狀態(tài)下的時(shí)間復(fù)雜度：

┌─────────┬─────┬──────┬──────┐
│ 初始文件狀態(tài) │   正序   │     反序  │無(wú)序(平均)│
├─────────┼─────┼──────┼──────┤
│ 第i趟的關(guān)鍵    │   1      │     i+1    │（i-2）/2│
│ 字比較次數(shù)     │          │              │             │
├─────────┼─────┼──────┼──────┤
│總關(guān)鍵字比較次數(shù)  │n-1 │(n+2)(n-1)/2│ ≈n2/4│
├─────────┼─────┼──────┼──────┤
│第i趟記錄移動(dòng)次數(shù) │ 0   │     i+2    │ （i-2）/2│
├─────────┼─────┼──────┼──────┤
│總的記錄移動(dòng)次數(shù)  │ 0   │(n-1)(n+4)/2│ ≈n2/4│
├─────────┼─────┼──────┼──────┤
│時(shí)間復(fù)雜度     │  0（n）│ O（n2） │ O（n2）│
└─────────┴─────┴──────┴──────┘

注意：初始文件按關(guān)鍵字遞增有序，簡(jiǎn)稱"正序"。初始文件按關(guān)鍵字遞減有序，簡(jiǎn)稱"反序"。

2．算法的空間復(fù)雜度分析

算法所需的輔助空間是一個(gè)監(jiān)視哨，輔助空間復(fù)雜度 S(n)=O(1)。是一個(gè)就地排序。

3．直接插入排序的穩(wěn)定性

直接插入排序是穩(wěn)定的排序方法。

上一篇：各種內(nèi)部排序方法的比較和選擇下一篇：冒泡排序

在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

直接插入排序

直接插入排序基本思想

一趟直接插入排序方法

直接插入排序算法

給定輸入實(shí)例的排序過(guò)程

算法分析