Shell 排序基本資訊

Shell 排序 ，也稱為遞減遞增排序，是最古老的排序演算法之一，以其發明者 Donald命名。 L. Shell （1959）。它快速，易於理解且易於實施。但是，它的複雜性分析稍微複雜一些。

Shell 排序的想法如下：

1. 將資料序列排列成二維陣列
2. 對陣列的列進行排序

Shell 排序改進了插入排序。它首先比較相距較遠的元素，然後比較相距較遠的元素，最後比較相鄰元素（實際上是插入排序）。

結果是資料序列被部分排序。重複上述過程，但每次都使用較窄的陣列，即列數較少。在最後一步中，陣列只包含一列。

Shell 排序示例：

https://i.stack.imgur.com/WTd9p.jpg

Shell 排序的虛擬碼：

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

輔助空間： O(n) total, O(1) auxiliary
時間複雜度： O(nlogn)