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)