Shell 排序

Harshit Jindal 2023年10月12日
  1. Shell 排序演算法
  2. Shell 排序示例
  3. Shell 排序演算法實現
  4. Shell 排序演算法的複雜度
Shell 排序

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

Shell 的原始序列 N/2,N/4,...,1
Papernov & Stasevich 增量 1, 3, 5, 9,...
Hibbard 的增量 1, 3, 7, 15, 31, 63,...
Knuth 的增量 1, 4, 13, ... , (3k – 1) / 2
Pratt 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, ....
Sedgewick 的增量 1, 8, 23, 77, 281, ... 4j+1+ 3-2j+ 1

Shell 排序演算法

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

  • 按照序列計算 gap 的值。
  • 對每一個間隔等於 gap 的子陣列進行如下操作。
  • 用插入排序法進行排序。
  • 重複上述過程,直到整個陣列被排序。

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)2)。

  • 最壞情況

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

  • 最佳情況

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

空間複雜度

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

作者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Sort Algorithm