啪啪拉拉噼里啪啦

直接插入排序基本思想

1、基本思想
    　假設(shè)待排序的記錄存放在數(shù)組R[1..n]中。初始時，R[1]自成1個有序區(qū)，無序區(qū)為R[2..n]。從i=2起直至i=n為止，依次將R[i]插入當前的有序區(qū)R[1..i-1]中，生成含n個記錄的有序區(qū)。

2、第i-1趟直接插入排序：
    　通常將一個記錄R[i](i=2，3，…，n-1)插入到當前的有序區(qū)，使得插入后仍保證該區(qū)間里的記錄是按關(guān)鍵字有序的操作稱第i-1趟直接插入排序。
    　排序過程的某一中間時刻，R被劃分成兩個子區(qū)間R[1．．i-1]（已排好序的有序區(qū)）和R[i．．n]（當前未排序的部分，可稱無序區(qū)）。
    　直接插入排序的基本操作是將當前無序區(qū)的第1個記錄R[i]插人到有序區(qū)R[1．．i-1]中適當?shù)奈恢蒙希筊[1．．i]變?yōu)樾碌挠行騾^(qū)。因為這種方法每次使有序區(qū)增加1個記錄，通常稱增量法。
    　插入排序與打撲克時整理手上的牌非常類似。摸來的第1張牌無須整理，此后每次從桌上的牌(無序區(qū))中摸最上面的1張并插入左手的牌(有序區(qū))中正確的位置上。為了找到這個正確的位置，須自左向右(或自右向左)將摸來的牌與左手中已有的牌逐一比較。

一趟直接插入排序方法

1．簡單方法
    　首先在當前有序區(qū)R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然后將R[k．．i-1]中的記錄均后移一個位置，騰出k位置上的空間插入R[i]。
  注意：
    　若R[i]的關(guān)鍵字大于等于R[1．．i-1]中所有記錄的關(guān)鍵字，則R[i]就是插入原位置。

2．改進的方法
　　一種查找比較操作和記錄移動操作交替地進行的方法。
具體做法：
    　將待插入記錄R[i]的關(guān)鍵字從右向左依次與有序區(qū)中記錄R[j](j=i-1，i-2，…，1)的關(guān)鍵字進行比較：
    　① 若R[j]的關(guān)鍵字大于R[i]的關(guān)鍵字，則將R[j]后移一個位置；
      ②若R[j]的關(guān)鍵字小于或等于R[i]的關(guān)鍵字，則查找過程結(jié)束，j+1即為R[i]的插入位置。
    　關(guān)鍵字比R[i]的關(guān)鍵字大的記錄均已后移，所以j+1的位置已經(jīng)騰空，只要將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大于等于有序區(qū)中所有的keys，則R[i]
                              //應在原有位置上
        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)； //當R[i].key≥R[j].key時終止
        R[j+1]=R[0]； //R[i]插入到正確的位置上
       }//endif
   }//InsertSort