Shell 排序

1. Shell 排序演算法
2. Shell 排序示例
3. Shell 排序演算法實現
4. Shell 排序演算法的複雜度

Shell 排序是一種高效的基於比較的排序演算法。它被看作是氣泡排序演算法的泛化，或者說是一種優化的插入排序演算法。在插入排序演算法中，我們將元素向前移動一個位置。但在 shell 排序的情況下，我們將元素 h 位置前移。它先對很遠的元素進行排序，然後根據序列逐步縮小差距，對整個陣列進行排序。使用的一些序列是：

Shell 排序演算法

假設我們有一個未排序的陣列 A[]，包含 n 元素。我們將使用 shell 的原始序列對陣列進行排序。

Shell 排序示例

假設我們有一個陣列：(9, 8, 3, 7, 5, 6, 4, 1)。我們將使用 shell 排序演算法對其進行排序，並使用 shell 的原始序列來減少間隙間隔。

• 第一次迭代

n/2=4，位於區間 4 的元素進行比較和交換。

A[0] > A[4] →交換，(5,8,3,7,9,6,4,1)。

A[1] > A[5] →交換，(5,6,3,7,9,8,4,1)。

A[2] < A[6]。

A[3] > A[7] →交換，(5,6,3,1,9,8,4,7)。

陣列變成：(5,6,3,1,9,8,4,7)。

• 第二次迭代

n/4=2，位於區間 2 的元素進行比較和交換。

A[0] > A[2] →交換，(3,6,5,1,9,8,4,7)。

A[1] > A[3] →交換，(3,1,5,6,9,8,4,7)。

A[0] < A[2] < A[4]。

A[1] < A[3] < A[5]。

A[2]>A[4] 和 A[4]>A[6]→交換，(3,1,4,6,5,8,9,7)。

A[1]<A[3]<A[5]，但 A[5]>A[7]→互換，(3,1,4,6,5,7,9,8)。

陣列變成：(3,1,4,6,5,7,9,8)。

• 第三次迭代

n/8=1 , 位於區間 1 的元素進行比較和交換。

A[0] > A[1] →交換，(1,3,4,6,5,7,9,8)。

A[0] ... A[2]→排序

A[0] ... A[3] → 排序的。

A[0] ... A[3] → 排序，但 A[3] > A[4] →交換，(1,3,4,5,6,7,9,8)。

A[0] ... A[5] → 排序完畢

A[0] ... A[6] → 排序的。

A[0] ... A[6]→排序，但 A[6] > A[7] →交換，(1，3，4，5，6，7，8，9)。

Shell 排序演算法實現

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Shell 排序演算法的複雜度

時間複雜度

• 平均情況

複雜度取決於選擇的排序序列。時間複雜度為 [Big Theta]：O(nlog(n)²)。

• 最壞情況

Shell 排序的最壞情況下時間複雜度總是小於等於 O(n²)。更準確的說根據 Poonen 定理，它由Θ(nlogn)²/(log log n)²)或Θ(nlog n)²/log log n)或Θ(n(log n)²)或介於兩者之間。最壞情況下的時間複雜度是 [Big O]：<= O(n²)。

• 最佳情況

最好的情況是當陣列已經排序，並且每個間隔所需的比較與陣列的大小相同。最佳情況下的時間複雜度為 [Big Omega]：O(nlogn)。

空間複雜度

Shell 排序演算法的空間複雜度為 O(n)，因為除了一個臨時變數外，不需要額外的記憶體。