排序 - 插入排序 - 直接插入排序（一）

　　插入排序(Insertion Sort)的基本思想是每次將一個待排序的記錄按其關鍵字大小插入到前面已經排好序的子文件中的適當

　　位置直到全部記錄插入完成為止

　　本節介紹兩種插入排序方法直接插入排序和希爾排序

　　直接插入排序基本思想

　　基本思想

　　假設待排序的記錄存放在數組R[n]中初始時R[]自成個有序區無序區為R[n]從i=起直至i=n為止依次將

　　R[i]插入當前的有序區R[i]中生成含n個記錄的有序區

　　第i趟直接插入排序

　　通常將一個記錄R[i](i=…n)插入到當前的有序區使得插入後仍保證該區間裡的記錄是按關鍵字有序的操作稱第i

　　趟直接插入排序

　　排序過程的某一中間時刻R被劃分成兩個子區間R[i](已排好序的有序區)和R[in](當前未排序的部分可稱無

　　序區)

　　直接插入排序的基本操作是將當前無序區的第個記錄R[i]插人到有序區R[i]中適當的位置上使R[i]變為新的有

　　序區因為這種方法每次使有序區增加個記錄通常稱增量法

　　插入排序與打撲克時整理手上的牌非常類似摸來的第張牌無須整理此後每次從桌上的牌(無序區)中摸最上面的張並插入左

　　手的牌(有序區)中正確的位置上為了找到這個正確的位置須自左向右(或自右向左)將摸來的牌與左手中已有的牌逐一比較

　　一趟直接插入排序方法

　　簡單方法

　　首先在當前有序區R[i]中查找R[i]的正確插入位置k(≤k≤i);然後將R[ki]中的記錄均後移一個位置騰出k位

　　置上的空間插入R[i]

　　注意

　　若R[i]的關鍵字大於等於R[i]中所有記錄的關鍵字則R[i]就是插入原位置

　　改進的方法

　　一種查找比較操作和記錄移動操作交替地進行的方法

　　具體做法

　　將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=ii…)的關鍵字進行比較

　　① 若R[j]的關鍵字大於R[i]的關鍵字則將R[j]後移一個位置;

　　②若R[j]的關鍵字小於或等於R[i]的關鍵字則查找過程結束j+即為R[i]的插入位置

　　關鍵字比R[i]的關鍵字大的記錄均已後移所以j+的位置已經騰空只要將R[i]直接插入此位置即可完成一趟直接插入排序

　　直接插入排序算法

　　算法描述

　　void lnsertSort(SeqList R)

　　{ //對順序表R中的記錄R[n]按遞增序進行插入排序

　　int ij;

　　for(i=;i<=n;i++) //依次插入R[]…R[n]

　　if(R[i]key

　　//應在原有位置上

　　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+1]=R[0]; //R[i]插入到正確的位置上

　　}//endif

　　}//InsertSort

From:http://tw.wingwit.com/Article/program/sjjg/201311/23808.html