梳排序

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)，因为除了临时变量外，梳排序算法不需要额外的空间。