梳排序
梳排序是一種簡單的基於比較的排序演算法。它是氣泡排序在氣泡排序中,相鄰的元素在每一個段落/階段進行比較,並逐一消除反轉。另一方面,梳排序從使用大間隙開始,每次以 1.3
的收縮係數縮小間隙。梳排序只需一次交換就可以去除多個反轉。它是基於殺烏龜的思想。海龜是指列表末尾的小元素,它降低了氣泡排序的效率,殺死海龜可以顯著提高排序效能。
梳排序演算法
假設我們有一個包含 n
元素的無序陣列 A[]
。我們取收縮因子為 1.3
,因為經驗上發現它能給出最好的結果。
-
初始化變數
gap
為陣列的大小,變數swapped
為true
。 -
將常量變數
SHRINK_FACTOR
宣告為1.3
。 -
當
gap
不是 1 或swapped
設定為true
時,執行以下操作。-
設定
swapped
為false
。 -
設定
gap
為(int)gap/SHRINK_FACTOR
。 -
對於
0
到n - 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
=true
和 SHRINK_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 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