插入排序

算法思想

• 将資料分為兩部分:有序表,無序表;開始時有序表為空,無序表中全部是待排序資料,依次從無序表中取出待

  排序元素插入到有序表中的合适位置,使有序表中的元素保持有序,直到無序表為空,表示排序完成。

  例如:對數組使用插入排序

  

  紅色部分表示無序表,綠色部分表示有序表,直線箭頭表示挪動元素以留出空間,以便元素的插入,

  弧形箭頭表示目前待排序元素的插入位置;

代碼實作

• 使用C語言實作插入排序:

  bool InsertSort(int * pUnSortAry, int nArySize)
  {
    if (pUnSortAry == nullptr || nArySize <= 0)
    {
      return false;
    }
  
    for (int iIndex = 1; iIndex < nArySize; iIndex++)
    {
      int nCurrentValue = pUnSortAry[iIndex];
      int jIndex = iIndex - 1;
      for (; jIndex >= 0 && nCurrentValue < pUnSortAry[jIndex]; jIndex--)
      {
        pUnSortAry[jIndex + 1] = pUnSortAry[jIndex];
      }
      pUnSortAry[jIndex + 1] = nCurrentValue;
    }
  
    return true;
  }
        

  測試代碼如下:

  void printAry(const int * pAry, int nSize)
  {
    for (int iIndex = 0; iIndex < nSize; iIndex++)
    {
      printf("%d ", pAry[iIndex]);
    }
    printf("\n");
  }
  
  
  
  int main()
  {
    srand(time(NULL));
    int nAry[20];
    for (int iIndex = 0; iIndex < 10; iIndex++)
    {
      memset(nAry, 0, sizeof(nAry)/sizeof(nAry[0]));
      for (int jIndex = 0; jIndex < sizeof(nAry) / sizeof(nAry[0]); jIndex++)
      {
        nAry[jIndex] = rand() % 150;
      }
      printf("\r\n排序前:");
      printAry(nAry, sizeof(nAry) / sizeof(nAry[0]));
      InsertSort(nAry, sizeof(nAry) / sizeof(nAry[0]));
      printf("排序後:");
      printAry(nAry, sizeof(nAry) / sizeof(nAry[0]));
    }
  }
        

  結果:

  

時間複雜度分析

插入排序的核心代碼如下:假設數組大小為n

for (int iIndex = 1; iIndex < nArySize; iIndex++) //執行n次
 {
    int nCurrentValue = pUnSortAry[iIndex];        //執行n-1次
    int jIndex = iIndex - 1;                       //執行n-1次
    //執行t1+t2+....ti次, i=iIndex;
    for (; jIndex >= 0 && nCurrentValue < pUnSortAry[jIndex]; jIndex--) 
    {
      pUnSortAry[jIndex + 1] = pUnSortAry[jIndex]; //執行t1+t2+....ti-1次
    }
    pUnSortAry[jIndex + 1] = nCurrentValue; //執行n-1次
}
      

t1,t2,......,tn表示執行第iIndex次循環時,内層for循環執行的次數,那麼總的時間複雜度如下:

T(n) = n+3*(n-1)+ 2*(t1+t2+.....+tn) -1;

• 當數組中的所有元素排序前已經處于有序狀态時,那麼此時内層for循環執行隻執行一次判斷,是以此時的時間

  複雜度為T(n) = n+4*(n-1) = O(n);

• 當數組中的元素逆序時,此時當外層for循環第iIndex次執行時,内層for循環執行執行的次數:

  t1+t2+......+ti=1+2+3....+n =(1+n)n/2

  此時的時間複雜度T(n)=n+3(n-1)+(1+n)*n-1=O(n^2)

穩定性

插入排序是在一個已經有序的小序列的基礎上,一次插入一個元素。當然，剛開始這個有序的小序列隻有1個

元素，就是第一個元素。比較是從有序序列的末尾開始,也就是想要插入的元素和已經有序的最大者開始比起,

如果比它大則直接插入在其後面,否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的,

那麼插入元素把想插入的元素放在相等元素的後面。是以,相等元素的前後順序沒有改變,從原無序序列出去的

順序就是排好序後的順序,是以插入排序是穩定的.