梳排序

梳排序(Comb sort)是一種由Wlodzimierz Dobosiewicz於1980年所發明的不穩定排序算法，並由Stephen Lacey和Richard Box於1991年四月號的Byte雜誌中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在於消除烏龜，亦即在陣列尾部的小數值，這些數值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在陣列前端的大數值，不影響泡沫排序的效能。
在泡沫排序中，只比較陣列中相鄰的二項，即比較的二項的間距(Gap)是1，梳排序提出此間距其實可大於1，改自插入排序的希爾排序同樣提出相同觀點。梳排序中，開始時的間距設定為陣列長度，並在循環中以固定比率遞減，通常遞減率設定為1.3。在一次循環中，梳排序如同泡沫排序一樣把陣列從首到尾掃描一次，比較及交換兩項，不同的是兩項的間距不固定於1。如果間距遞減至1，梳排序假定輸入陣列大致排序好，並以泡沫排序作最後檢查及修正。遞減率

遞減率的設定影響著梳排序的效率，原作者以隨機數作實驗，得到最有效遞減率為1.3的。如果此比率太小，則導致一循環中有過多的比較，如果比率太大，則未能有效消除陣列中的烏龜。亦有人提議用

遞減率

作遞減率，同時增加換算表協助於每一循環開始時計算新間距。變異形式梳排序-11

設定遞減率為1.3時，最後只會有三種不同的間距組合：(9, 6, 4, 3, 2, 1)、(10, 7, 5, 3, 2, 1)、或 (11, 8, 6, 4, 3, 2, 1)。實驗證明，如果間距變成9或10時一律改作11，則對效率有明顯改善，原因是如果間距曾經是9或10，則到間距變成1時，數值通常不是遞增序列，故此要進行幾次泡沫排序循環修正。加入此指定間距的變異形式稱為梳排序-11(Combsort11)。

混合梳排序和其他排序算法

如同快速排序和合併排序，梳排序的效率在開始時最佳，接近結束時，即進入泡沫排序時最差。如果間距變得太小時(例如小於10)，改用諸如插入排序或雞尾酒排序等算法，則可提升整體效能。
此方法的最大好處是不再需要檢查有否進行過交換程式以將排序循環提早結束。

算法實現

C語言實現：
void comb_sort(int* data, int n)
{
const double shrink = 1.25;
int i, delta = n, noswap = 0;
while(!noswap)
{
for(noswap = 1, i = 0; i + delta < n; i++)
if(data&#91;i&#93; > data&#91;i + delta&#93;)
{
data&#91;i&#93; ^= data&#91;i + delta&#93;;
data&#91;i + delta&#93; ^= data&#91;i&#93;;
data&#91;i&#93; ^= data&#91;i + delta&#93;;
noswap = 0;
}
if(delta > 1)
{
delta /= shrink;
noswap = 0;
}
}
}