梳排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 梳排序演算法
  2. 梳排序示例
  3. 梳排序演算法的實現
  4. 梳排序演算法複雜度
梳排序

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

梳排序演算法

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

  • 初始化變數 gap 為陣列的大小,變數 swappedtrue
  • 將常量變數 SHRINK_FACTOR 宣告為 1.3
  • gap 不是 1 或 swapped 設定為 true 時,執行以下操作。
    • 設定 swappedfalse
    • 設定 gap(int)gap/SHRINK_FACTOR
    • 對於 0n - gap 範圍內的每個元素,執行以下操作 - 如果 A[i]>A[i+gap],則 swap(A[i], A[i+gap]),並將 swapped 設為 true

梳排序示例

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

初始化 gap=8 , swapped=trueSHRINK_FACTOR=1.3

  • 第一遍

gap=8/1.3=6,swapped=false

迭代 (3, 5, 2, 8, 1, 7, 6, 4) 動作
i = 0 (3, 5, 2, 8, 3, 7, 6, 4) 3<6,不交換
i = 1 (3, 4, 2, 8, 1, 7, 6, 5) 5>4, 交換
  • 第二遍

gap=6/1.3=4,swapped=false

迭代 (3, 4, 2, 8, 1, 7, 6, 5) 動作
i = 0 (1, 4, 2, 8, 3, 7, 6, 5) 3>1,交換
i = 1 (1, 4, 2, 8, 3, 7, 6, 5) 4<7,不交換
i = 2 (1, 4, 2, 8, 3, 7, 6, 5) 2<6,不交換
i = 3 (1, 4, 2, 5, 3, 7, 6, 8) 8>5, 交換
  • 第三遍

gap= 4/1.3 = 3,swapped=false

迭代 (1, 4, 2, 5, 3, 7, 6, 8) 動作
i = 0 (1, 4, 2, 5, 3, 7, 6, 8) 1<5,不交換
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 4>3,交換
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2<7,不交換
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5<6,不交換
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4<8,不交換
  • 第四遍

gap=3/1.3=2,swapped=false

迭代 (1, 3, 2, 5, 4, 7, 6, 8) 動作
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1<2,不交換
i = 1 (1, 3, 2, 5, 4, 7, 6, 8) 3<5,不交換
i = 2 (1, 3, 2, 5, 4, 7, 6, 8) 2<4,不交換
i = 3 (1, 3, 2, 5, 4, 7, 6, 8) 5<7,不交換
i = 4 (1, 3, 2, 5, 4, 7, 6, 8) 4<6,不交換
i = 5 (1, 3, 2, 5, 4, 7, 6, 8) 7<8,不交換
  • 第五遍

gap=2/1.3=1,swapped=false

迭代 (1, 3, 2, 5, 4, 7, 6, 8) 動作
i = 0 (1, 3, 2, 5, 4, 7, 6, 8) 1<3,不交換
i = 1 (1, 2, 3, 5, 4, 7, 6, 8) 3>2,交換
i = 2 (1, 2, 3, 5, 4, 7, 6, 8) 3<5,不交換
i = 3 (1, 2, 3, 4, 5, 7, 6, 8) 5>4, 交換
i = 4 (1, 2, 3, 4, 5, 7, 6, 8) 5<7,不交換
i = 5 (1, 2, 3, 5, 4, 6, 7, 8) 7>6, 交換
i = 6 (1, 2, 3, 4, 5, 6, 7, 8) 7<8,不交換

我們得到最終的排序陣列為: (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(n2/2p) 其中 p 是增量的數量。

  • 最壞情況

最壞情況下的時間複雜度為 [BigO]:O(n2)。

  • 最佳情況

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

空間複雜度

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

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