直接插入排序
插入排序(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．算法描述
Java代碼
- 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
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)。是一個就地排序。
3．直接插入排序的穩定性
直接插入排序是穩定的排序方法。
算法程式
Java代碼
- void insertsort(int n,int[])
- //插入排序法
- //從第二個元素開始每次插入一個元素。将比要插入的元素值大的元素依次後移
- //算法複雜度n^2
- //直接插入排序是穩定的排序方法。
- {
- int i,j,tmp;
- for(i=1;i<n;i++)
- {
- tmp=a[i];
- j=i-1;
- while(tmp<a[j]&&j>=0)
- {
- a[j+1]=a[j];
- j=j-1;
- }
- a[j+1]=tmp;
- }
- }
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)