排序——希爾排序

希爾排序（基于逐趟縮小增量）

基本思想

• 先将整個待排記錄序列分割成若幹子序列,分别進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。

算法實作

void ShellSort(SqList &L, int dlta[], int t){
    // 按增量序列dlta[0…t-1]對順序表L作Shell排序
    for(k = 0; k < t; k++)
        ShellInsert(L, dlta[k]);  // 增量為dlta[k]的一趟插入排序

}

void ShellInsert(SqList &L, int dk){
    // 對順序表L進行一趟增量為dk的Shell排序，dk為步長因子
    for(i = dk + 1; i <= L.length; i++){
        // 開始将r[i] 插入有序增量子表
        if(r[i].key < r[i - dk].key){
            r[0] = r[i];  // 暫存在r[0]
            for(j = i - dk; j > 0 && (r[0].key < r[j].key); j = j - dk)
                r[j + dk] = r[j];  // 關鍵字較大的記錄在子表中後移
            r[j + dk] = r[0];  // 在本趟結束時将r[i]插入到正确位置
        }
    }
}           

算法分析

• 時間複雜度： O（n3/2） 　
• 空間複雜度為 O(1)
• 穩定性： 不穩定

如何選擇最佳的序列，目前尚未解決

最後一個增量值必須為1，無除1以外的公因子

不宜在鍊式存儲結構上實作