2025-02-10

插入排序 Insertion Sort
插入排序的基本思想是,經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置,使得L[1..i] 又是排好序的序列。要達到這個目的,我們可以用順序比較的方法。首先比較L[i]和L[i-1],如果L[i-1]≤ L[i]?騆[1..i]已排好序,第i遍處理就結束瞭;否則交換L[i]與L[i-1]的位置,繼續比較L[i-1]和L[i-2],直到找到某一個位置j(1≤j≤i-1),使得L[j] ≤L[j 1]時為止。
  簡言之,插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置,直到全部插入完畢。插入排序方法分直接插入排序和折半插入排序兩種,這裡隻介紹直接插入排序,折半插入排序留到“查找”內容中進行。
  圖1演示瞭對4個元素進行直接插入排序的過程,共需要(a),(b),(c)三次插入。

圖1 對4個元素進行插入排序
在下面的插入排序算法中,為瞭寫程序方便我們可以引入一個哨兵元素L[0],它小於L[1..n]中任一記錄。所以,我們設元素的類型 ElementType中有一個常量-∞,它比可能出現的任何記錄都小。如果常量-∞不好事先確定,就必須在決定L[i]是否向前移動之前檢查當前位置是否為1,若當前位置已經為1時就應結束第i遍的處理。另一個辦法是在第i遍處理開始時,就將L[i]放入L[0]中,這樣也可以保證在適當的時候結束第i 遍處理。下面的算法中將對當前位置進行判斷。
算法如下:
    /**
     *插入排序(WHILE循環實現)
     *@paramsrc待排序數組
     */
    void doInsertSort1(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i )
       {  
           int temp=src[i];
           int j=i;
          
           while(src[j-1]>temp)
           {
              src[j]=src[j-1];
              j–;
              if(j<=0)
                  break;
           }
           src[j]=temp;
           printResult(i 1,src);
       }
    }
    /**
     *插入排序(FOR循環實現)
     *@paramsrc待排序數組
     */
    void doInsertSort2(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i )
       {
           int j;
           int temp=src[i];
           for(j=i;j>0;j–)
           {
              if(src[j-1]>temp)
              {
                  src[j]=src[j-1];
                 
              }else//如果當前的數,不小前面的數,那就說明不小於前面所有的數,
                   //因為前面已經是排好瞭序的,所以直接通出當前一輪的比較
                  break;
           }
           src[j]=temp;
           printResult(i,src);
       }
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *