梳排序

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

梳排序是一種簡單的基於比較的排序演算法。它是氣泡排序的改進形式。在氣泡排序中，相鄰的元素在每一個段落/階段進行比較，並逐一消除反轉。另一方面，梳排序從使用大間隙開始，每次以 1.3 的收縮係數縮小間隙。梳排序只需一次交換就可以去除多個反轉。它是基於殺烏龜的思想。海龜是指列表末尾的小元素，它降低了氣泡排序的效率，殺死海龜可以顯著提高排序效能。

梳排序演算法

假設我們有一個包含 n 元素的無序陣列 A[]。我們取收縮因子為 1.3，因為經驗上發現它能給出最好的結果。

梳排序示例

假設我們有陣列：(3, 5, 2, 8, 1, 7, 6, 4). 我們將使用梳排序演算法對其進行排序。

初始化 gap=8 , swapped=true 和 SHRINK_FACTOR=1.3。

• 第一遍

gap=8/1.3=6，swapped=false。

• 第二遍

gap=6/1.3=4，swapped=false。

• 第三遍

gap= 4/1.3 = 3，swapped=false。

• 第四遍

gap=3/1.3=2，swapped=false。

• 第五遍

gap=2/1.3=1，swapped=false。

我們得到最終的排序陣列為： (1, 2, 3, 4, 5, 6, 7, 8)。

梳排序演算法的實現

#include <iostream>
using namespace std;

int updateGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  bool swapped = true;
  while (gap > 1 || swapped == true) {
    gap = updateGap(gap);
    swapped = false;
    for (int i = 0; i < (n - gap); i++) {
      int temp;
      if (arr[i] > arr[i + gap]) {
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  combSort(arr, n);
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

梳排序演算法複雜度

時間複雜度

• 平均情況

時間複雜度為 [O Theta]級：O(n²/2^p) 其中 p 是增量的數量。

• 最壞情況

最壞情況下的時間複雜度為 [BigO]：O(n²)。

• 最佳情況

最好的情況發生在陣列已經排序或接近排序的時候。最佳情況下的時間複雜度是 [Big Omega]：O(nlogn)。它比氣泡排序的最佳情況時間複雜度有很大的改進。

空間複雜度

該演算法的空間複雜度為 O(n)，因為除了臨時變數外，梳排序演算法不需要額外的空間。