希爾排序 (Shell Sort)

程式資結演算法

Written by:

希爾排序法 (Shell Sort) 是插入排序法 (Insertion Sort) 的改良版,因為簡單、效率不錯,在實際應用上的接受度頗高。

Insertion Sort 在資料幾乎已經排序好的情況下,時間複雜度越接近 O(n)。也就是說,Shell Sort 是基於插入排序的以下兩點性質而提出改進方法的:

  •  Insertion Sort 在對幾乎已經排好序的資料操作時,效率高,即可以達到線性排序的效率
  • 但 Insertion Sort 一般來說是低效率的,因為每次只能將資料移動一位

Shell Sort 提出的概念是──將整個陣列依照預先指定的間隔長度 d,交錯分割成數個小陣列,並以插入排序的方式將這些小陣列個別排序,然後逐漸縮小間隔長度 d ,直到 d 等於 1。

此時再作最後一次插入排序。

步驟

  • 由大到小選定數個間距 (span)
  • for i = 1 to (n-span) do
    • 將資料依指定的 span 分組,進行插入排序──比較第 i 筆與第 i+span 筆資料,若前者大於後者,則交換前後資料
    • 每一回合必須持續做到沒有交換 (No SWAP) 和 span 為 1 為止,才可結束本回合進入下一回合
  • 回合數是由 span 的型式所決定

若某回合的 span 值為 k,則表示有 k 個小陣列要排序好,每個小陣列的資料量大約是 n/k 。

常見的 Span 型式

1. 

2.

 

虛擬碼

 

程式碼

 

時間複雜度

1. Worst Case: O(n2)

2. Average: O(n2)

2. Best Case: 到目前為止尚無定論,與 Span 的型式有關。可能有 O(n3/2)、O(n3/4)、O(n7/6)

 

空間複雜度:o(1)

需要一個額外的空間,紀錄目前欲插入的資料,即暫存用來交換的 temp 變數。

 

穩定性:Unstable

可以發現 5 和 5* 在中間過程中交換了,可知為 Unstable Sorting。

One Reply to “希爾排序 (Shell Sort)”

  1. Roy Lo 說:

    你的程式碼好像忘了把flag加進去!

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *