梳排序

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