希爾排序 (Shell Sort)

希爾排序法 (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. 

n = 10
-----------------
Pass 1: span = 5
Pass 2: span = 2
Pass 3: span = 1

2.

Pass 1: span = 15 = 2^4-1
Pass 2: span = 7 = 2^3-1
Pass 3: span = 3 = 2^2-1
Pass 4: span = 1 = 2^1-1

 

虛擬碼

ShellSort(A[], n)
  span = n/2
  while (span>-1) do
  repeat
  flag = 0 //有無swap發生?
  for i = 1 to (n-span) do
  if(A[i] > A[i+1]) then
    swap(A[i] > A[i+span])
    flag = 1
  until (flag == 0) //持續做到沒有交換為止
  span = span/2 //下一個回合的span

 

程式碼

void swap(int *a, int *b){
  int temp;
  temp = *a;
  *a = *b;
  *b= temp;
};

int shell_sort(int A[], int n){
  int span, i;
  span = n/2;
  while(span>=1){
    for(i = 0; i<(n-span); i++){
      if(A[i]>A[i+span]){
        swap(&A[i], &A[i+span]);
      }
    }
    span = span/2;
  }
};

int main(){
  int count, i;
  scanf("%d", &count);
  int list[count];
  printf("Numbers to be sorted: ");
  for(i = 0; i<count; i++){
    scanf("%d", &list[i]);
    printf("%d ", list[i]);
  }
  printf("\n");
  shell_sort(list, count);
  printf("Numbers Sorted: ");
  for(i = 0; i<count; i++){
    printf("%d ", list[i]);
  }
  return 0;
}

 

時間複雜度

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

Pass 0
--------------------------------- 
array index: [0] [1] [2] [3]
input data:   5   5*  3   8

Pass 1: Span = 2
--------------------------------- 
array index: [0] [1] [2] [3]
input data:   3   5*  5   8

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