三種插入排序的分析

插入排序(Insertion Sort)的基本思想是：每次将一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子檔案中的适當位置，直到全部記錄插入完成為止。

一、直接插入排序

直接插入排序（insert sorting)思想：當插入第i個元素時，前面的v[0],v[1],v[2]......v[i-1],已經排好序了.這時用v[i]的插入碼與v[i-1],v[i-2],......排序碼進行比較，找到插入的位置即插入v[i],原來位置上的元素從後向前依次後移。

template<class T>

void InsertSort(T a[],int n)

{

     for (int i = 1;i < n;++i)

     {

          int tmp = a[i];

          int j;

          for (j = i-1;j >= 0&&a[j]>tm p;--j)

               a[j+1] = a[j];

          a[j+1] = tmp;

     }

}

時間複雜度：

從時間分析，首先外層循環要進行n-1次插入，每次插入最少比較一次（正序），移動兩次；最多比較i次，移動i＋2次（逆序）（i=1，2，…，n-1）。若分别用Cmin ，Cmax 和Cave表示元素的總比較次數的最小值、最大值和平均值，用Mmin ，Mmax 和Mave表示元素的總移動次數的最小值、最大值和平均值，則上述直接插入算法對應的這些量為：

Cmin=n-1 Mmin=2（n-1）

Cmax=1+2+…+n-1=（n^2-n）/2 Mmax=3+4+…+n+1=（n^2+3n-4）/2

Cave=（n^2+n-2）/4 Mmax=（n^2+7n-8）/4

是以，直接插入排序的時間複雜度為O（n^2）。

由上面對時間複雜度的分析可知,當待排序元素已從小到大排好序(正序)或接近排好序時,所用的比較次數和移動次數較少;當待排序元素已從大到小排好序(逆序)或接近排好序時,所用的比較次數和移動次數較多,是以插入排序更适合于原始資料基本有序(正序)的情況.

插入法雖然在最壞情況下複雜性為O(n^2)，但是對于小規模輸入來說，插入排序法是一個快速的排序法。許多複雜的排序法，在規模較小的情況下，都使用插入排序法來進行排序，比如快速排序。

空間複雜度：

首先從空間來看，它隻需要一個元素的輔助空間，用于元素的位置交換O(1)。

穩定性：

插入排序是穩定的,因為具有同一值的元素必然插在具有同一值得前一個元素的後面,即相對次序不變.

适用情況：

插入排序是一種簡單的排序方法,他不僅适用于順序存儲結構(數組),而且适用于連結存儲結構,不過在連結存儲結構上進行直接插入排序時,不用移動元素的位置,而是修改相應的指針。

二、二分插入法

二分（折半）插入（Binary insert sort)排序基本思想：設在資料表中有一個元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已經排好序的元素。在插入v[i]。利用折半搜尋尋找v[i]的插入位置。

二分插入排序是一種穩定的排序。當n較大時，總排序碼比較次數比直接插入排序的最差情況好得多，但比最好情況要差，所元素初始序列已經按排序碼接近有序時，直接插入排序比二分插入排序比較次數少。二分插入排序元素移動次數與直接插入排序相同，依賴于元素初始序列。

template<class T>

void BinaryInsertSort(T a[],int n)

{

    for (int i = 1;i < n;++i)

    {

         int left = 0,

         right = i-1;

         int tmp = a[i];

         while (left <= right)

        {

              int middle = (left+right)/2;

              if (a[i]<a[middle])

                   right = middle-1;

              else

                   left = middle+1;   

        }

        int j;

        for (j = i-1;j>=left;--j)

             a[j+1] = a[j];

       a[j+1] = tmp;

    }

}

三、希爾排序

基本思想：先取一個小于n的整數d1作為第一個增量，把檔案的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組内進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有記錄放在同一組中進行直接插入排序為止。

增量序列的選擇：

Shell排序的執行時間依賴于增量序列。 好的增量序列的共同特征： ① 最後一個增量必須為1； ② 應該盡量避免序列中的值(尤其是相鄰的值）互為倍數的情況。 有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在n到1.6n之間。 參考代碼： template<class T> void ShellSort(T a[],int n) {     for (int gap = n/2;gap >= 1;gap/=2)     {          for (int i = gap;i < n;++i)          {               int tmp = a[i];               int j;               for (j = i-gap;j >= 0&&a[j] > tmp;j-=gap)                     a[j+gap] = a[j];               a[j+gap] = tmp;          }                        } }

性能分析：

希爾排序的時間性能優于直接插入排序的原因：

　　①當檔案初态基本有序時直接插入排序所需的比較和移動次數均較少。

　　②當n值較小時，n和n2的差别也較小，即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度0(n2)差别不大。

　　③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組内直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使檔案較接近于有序狀态，是以新的一趟排序過程也較快。

    　是以，希爾排序在效率上較直接插人排序有較大的改進。

穩定性：

希爾排序是不穩定的。