排序算法三：Shell插入排序

---

 

---

排序相關的的基本概念

排序：將一組雜亂無章的數據按一定的規律順次排列起來。
數據表( data list): 它是待排序數據對象的有限集合。 排序碼(key):通常數據對象有多個屬性域，即多個數據成員組成,其中有一個屬性域可用來區分對象,作為排序依據。該域即為排序碼。每個數據表用哪個屬性域作為排序碼，要視具體的應用需要而定。 分類
內排序：指在排序期間數據對象全部存放在內存的排序； 外排序：指在排序期間全部對象個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。

---

排序算法的分析

排序算法的穩定性

如果在對象序列中有兩個對象r[i]和r[j] ,它們的排序碼k[i]==k[j] 。如果排序前後,對象r[i]和r[j] 的相對位置不變，則稱排序算法是穩定的；否則排序算法是不穩定的。

排序算法的評價

時間開銷

排序的時間開銷可用算法執行中的數據比較次數與數據移動次數來衡量。 算法運行時間代價的大略估算一般都按平均情況進行估算。對於那些受對象排序碼序列初始排列及對象個數影響較大的，需要按最好情況和最壞情況進行估算

空間開銷

算法執行時所需的附加存儲。

---

Shell插入排序

基本思想

先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然後，取第二個增量d2重復上述的分組和排序，直至所取的增量dt=1(dt，即所有記錄放在同一組中進行直接插入排序為止。該方法實質上是一種分組插入方法。實際上當dt=1時，完全就是直接插入排序。但是經過多個分組的直接插入排序，最後一次完整的插入排序前數據表幾乎已經是排好序了，因此shell sort充分利用了直接插入排序在數據表幾乎已經有序的條件下工作高效的特點。

算法的C plus plus實現

根據算法的基本思想，shell插入排序的實現還是比較容易的，其C++實現如下：

#include 
#include 
using namespace std;

void print(int ar[], int sz, int step)
{   
    for(int i = 0; i < sz; ++i) { 
        if(((i + 1) % step) != 0)
            cout << setw(3) << ar[i]; 
        else
            cout << setw(3) << ar[i] << endl;

    }
    cout << endl;
}

void ShellSort(int a[], int sz)
{
    int i, j;
    int step, temp;
    step = sz / 2 ;
    while(step) {
        print(a, sz, step);
        cout << ==> << endl;
        for (i = step; i < sz; i++) {
            temp = a[i];
            j = i;
            while (j >= step && a[j - step] > temp) {
                a[j] = a[j - step];
                j = j - step;
            }
            a[j] = temp;
        }
        print(a, sz, step);
        cout << current array << endl;
        print(a, sz, sz);
        cout << ---------------- << endl;

        step = step / 2.2;
    }
}

int main(void)
{   
    int a[] = {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10};
    const size_t sz = sizeof(a)/sizeof(a[0]);

    cout << Initial array << endl;
    print(a,sz,sz);
    cout << ------------- << endl;

    ShellSort(a,sz); 

    cout << Sorted array  << endl;
    print(a,sz,sz); 
    return 0;
}

核心部分ShellSort中內層的while循環實現的是查找相應組內的插入位置，並提前進行位置的交換。而for循環控制的是從每個組內的第2個數開始重復在該組前面有序的數據表中實現直接插入排序。與直接插入排序的區別是shell插入排序一次for將所有組內的第i個數插入到各自前i-1個有序表中。

輸出為：

Initial array
 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

-------------
 13 14 94 33 82 25 59 94
 65 23 45 27 73 25 39 10

==>
 13 14 45 27 73 25 39 10
 65 23 94 33 82 25 59 94

current array
 13 14 45 27 73 25 39 10 65 23 94 33 82 25 59 94

----------------
 13 14 45
 27 73 25
 39 10 65
 23 94 33
 82 25 59
 94
==>
 13 10 25
 23 14 33
 27 25 45
 39 73 59
 82 94 65
 94
current array
 13 10 25 23 14 33 27 25 45 39 73 59 82 94 65 94

----------------
 13
 10
 25
 23
 14
 33
 27
 25
 45
 39
 73
 59
 82
 94
 65
 94

==>
 10
 13
 14
 23
 25
 25
 27
 33
 39
 45
 59
 65
 73
 82
 94
 94

current array
 10 13 14 23 25 25 27 33 39 45 59 65 73 82 94 94

----------------
Sorted array
 10 13 14 23 25 25 27 33 39 45 59 65 73 82 94 94

算法分析

增量序列的選擇
Shell排序的執行時間依賴於增量序列。
好的增量序列的共同特征：
最後一個增量必須為1； 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6nl.25之間。 Shell排序的時間性能優於直接插入排序
希爾排序的時間性能優於直接插入排序的原因：
當數據表初態基本有序時直接插入排序所需的比較和移動次數均較少。 當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。 在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di−1作為距離排過序，使數據表較接近於有序狀態，所以新的一趟排序過程也較快。
因此，希爾排序在效率上較直接插人排序有較大的改進。 穩定性
希爾排序是不穩定的。兩個相同關鍵字在排序前後的相對次序是可能發生變化的。

這個方法對於大的數據集效率其實並不高，但是它是一個對小數量數據表（小於1000）進行排序的最快算法之一。另外，相對使用的內存較少。