梳排序

梳排序

使用梳排序為一列数字进行排序的过程
分類	排序算法
數據結構	陣列
最差時間復雜度	$O(n \log n)$
最差空間復雜度	$O(1)$

梳排序(Comb sort)是一種由Wlodzimierz Dobosiewicz於1980年所發明的不穩定排序算法，並由Stephen Lacey和Richard Box於1991年四月號的Byte雜誌中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在於消除烏龜，亦即在陣列尾部的小數值，這些數值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在陣列前端的大數值，不影響泡沫排序的效能。

在泡沫排序中，只比較陣列中相鄰的二項，即比較的二項的間距(Gap)是1，梳排序提出此間距其實可大於1，改自插入排序的希爾排序同樣提出相同觀點。梳排序中，開始時的間距設定為陣列長度，並在迴圈中以固定比率遞減，通常遞減率設定為1.3。在一次迴圈中，梳排序如同泡沫排序一樣把陣列從首到尾掃描一次，比較及交換兩項，不同的是兩項的間距不固定於1。如果間距遞減至1，梳排序假定輸入陣列大致排序好，並以泡沫排序作最後檢查及修正。

遞減率

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

亦有人提議用$1/\left(1-\frac{1}{e^\varphi}\right) \approx 1.247330950103979$作遞減率，同時增加換算表協助於每一迴圈開始時計算新間距。

變異形式

梳排序-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)，改用諸如插入排序或雞尾酒排序等算法，則可提昇整體效能。

此方法的最大好處是不再需要檢查有否進行過交換程序以將排序迴圈提早結束。

算法實現

算法

梳排序程序(以array作輸入)
    gap := array的長度 //設定開始時的間距
    
    一直迴圈至 gap <= 1 及 swaps = 0
        //更新間距
        gap := 取「gap除以遞減率」的整數值
        
        i := 0
        swaps := 0 //用以檢查陣列是否已在遞增形式，只限gap=1時有效
        
        //把輸入陣列「梳」一次
        一直迴圈至 i + gap >= array的長度 //從首到尾掃描一次
            如果 array[i] > array[i+gap]
                把array[i]和array[i+gap]的數值交換
                swaps := 1 // 曾作交換，故此陣列未必排序好
            如果部分結束
            i := i + 1
        迴圈結束
       
    迴圈結束
程序結束

C++ 語言

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;
 
    while ( (gap > 1) || (swaps == true) ){
        if (gap > 1)
            gap = static_cast<difference_type>(gap/shrink_factor);
 
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
 
        for ( ; itRight!=last; ++itLeft, ++itRight ){
            if ( (*itRight) < (*itLeft) ){
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

Java語言

public static <E extends Comparable<? super E>> void sort(E[] input) {
    int gap = input.length;
    boolean swapped = true;
    while (gap > 1 || swapped) {
        if (gap > 1) {
            gap = (int) (gap / 1.3);
        }
        int i = 0;
        swapped = false;
        while (i + gap < input.length) {
            if (input[i].compareTo(input[i + gap]) > 0) {
                E t = input[i];
                input[i] = input[i + gap];
                input[i + gap] = t;
                swapped = true;
            }
            i++;
        }
    }
}

C語言

void combsort(int *arr, int size) {
 
  float shrink_factor = 1.247330950103979;
  int gap = size, swapped = 1, swap, i;
 
  while ((gap > 1) || swapped) {
    if (gap > 1) gap = gap / shrink_factor;
 
    swapped = 0; 
    i = 0;
 
    while ((gap + i) < size) {
      if (arr[i] - arr[i + gap] > 0) {
        swap = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = swap;
        swapped = 1;
      }
      ++i;
    }
  }
}

例

假設輸入為

8 4 3 7 6 5 2 1

目標為將之變成遞增排序。 因為輸入長度=8，開始時設定間距為8÷1.3≒6， 則比較8和2、4和1，並作交換兩次。

8 4 3 7 6 5 2 1

2 4 3 7 6 5 8 1

2 1 3 7 6 5 8 4

第二次迴圈，更新間距為6÷1.3≒4。比較2和6、1和5，直至7和4，此迴圈中只須交換一次。

2 1 3 7 6 5 8 4

2 1 3 4 6 5 8 7

接下來的每次迴圈，間距依次遞減為3 → 2 → 1，

間距=3時，不須交換

2 1 3 4 6 5 8 7

間距=2時，不須交換

2 1 3 4 6 5 8 7

間距h=1時，交換三次

2 1 3 4 6 5 8 7

1 2 3 4 6 5 8 7

1 2 3 4 5 6 8 7

1 2 3 4 5 6 7 8

上例中，共作了六次交換以完成排序。

參看

• 泡沫排序，梳排序的基本，較慢的算法。
• 雞尾酒排序，或雙向泡沫排序，一樣解決了泡沫排序中的烏龜問題。

外部鏈接

您可以在維基教科書中查找此百科条目的相關電子教程：

Sorting/Comb sort

• .NET Implementation of comb sort and several other algorithms
• Combsort - Who ever knew that bubblesort could be so good?