[科普中國]-梳排序

**梳排序（Comb sort）**是一種由Wlodzimierz Dobosiewicz于1980年所發(fā)明的不穩(wěn)定排序算法，并由Stephen Lacey和Richard Box于1991年四月號的Byte雜志中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在于消除烏龜，亦即在數(shù)組尾部的小數(shù)值，這些數(shù)值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在數(shù)組前端的大數(shù)值，不影響泡沫排序的性能。

在泡沫排序中，只比較數(shù)組中相鄰的二項(xiàng)，即比較的二項(xiàng)的間距（Gap）是1，梳排序提出此間距其實(shí)可大于1，改自插入排序的希爾排序同樣提出相同觀點(diǎn)。梳排序中，開始時的間距設(shè)置為數(shù)組長度，并在循環(huán)中以固定比率遞減，通常遞減率設(shè)置為1.3。在一次循環(huán)中，梳排序如同泡沫排序一樣把數(shù)組從首到尾掃描一次，比較及交換兩項(xiàng)，不同的是兩項(xiàng)的間距不固定于1。如果間距遞減至1，梳排序假定輸入數(shù)組大致排序好，并以泡沫排序作最后檢查及修正。

介紹**梳排序（Comb sort）**是一種由Wlodzimierz Dobosiewicz于1980年所發(fā)明的不穩(wěn)定排序算法，并由Stephen Lacey和Richard Box于1991年四月號的Byte雜志中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在于消除烏龜，亦即在數(shù)組尾部的小數(shù)值，這些數(shù)值是造成泡沫排序緩慢的主因。相對地，兔子，亦即在數(shù)組前端的大數(shù)值，不影響泡沫排序的性能。

在泡沫排序中，只比較數(shù)組中相鄰的二項(xiàng)，即比較的二項(xiàng)的間距（Gap）是1，梳排序提出此間距其實(shí)可大于1，改自插入排序的希爾排序同樣提出相同觀點(diǎn)。梳排序中，開始時的間距設(shè)置為數(shù)組長度，并在循環(huán)中以固定比率遞減，通常遞減率設(shè)置為1.3。在一次循環(huán)中，梳排序如同泡沫排序一樣把數(shù)組從首到尾掃描一次，比較及交換兩項(xiàng)，不同的是兩項(xiàng)的間距不固定于1。如果間距遞減至1，梳排序假定輸入數(shù)組大致排序好，并以泡沫排序作最后檢查及修正。1

排序算法在計(jì)算機(jī)科學(xué)與數(shù)學(xué)中，一個排序算法（英語：Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定排序方式進(jìn)行排列的一種算法。最常用到的排序方式是數(shù)值順序以及字典順序。有效的排序算法在一些算法（例如搜索算法與合并算法）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字?jǐn)?shù)據(jù)以及產(chǎn)生人類可讀的輸出結(jié)果?；旧?，排序算法的輸出必須遵守下列兩個原則：

輸出結(jié)果為遞增序列（遞增是針對所需的排序順序而言）

輸出結(jié)果是原輸入的一種排列、或是重組

雖然排序算法是一個簡單的問題，但是從計(jì)算機(jī)科學(xué)發(fā)展以來，在此問題上已經(jīng)有大量的研究。舉例而言，冒泡排序在1956年就已經(jīng)被研究。雖然大部分人認(rèn)為這是一個已經(jīng)被解決的問題，有用的新算法仍在不斷的被發(fā)明。1

遞減率遞減率的設(shè)置影響著梳排序的效率，原作者以隨機(jī)數(shù)作實(shí)驗(yàn)，得到最有效遞減率為1.3的。如果此比率太小，則導(dǎo)致一循環(huán)中有過多的比較，如果比率太大，則未能有效消除數(shù)組中的烏龜。

亦有人提議用作遞減率，同時增加換算表協(xié)助于每一循環(huán)開始時計(jì)算新間距。

因?yàn)榫幊陶Z言中乘法比除法快，故會取遞減率倒數(shù)與間距相乘，

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

混合梳排序和其他如同快速排序和合并排序，梳排序的效率在開始時最佳，接近結(jié)束時，即進(jìn)入泡沫排序時最差。如果間距變得太小時(例如小于10)，改用諸如插入排序或雞尾酒排序等算法，則可提升整體效能。

此方法的最大好處是不再需要檢查有否進(jìn)行過交換程序以將排序循環(huán)提早結(jié)束。1

偽代碼梳排序程序（以array作輸入） gap = array的長度//設(shè)定開始時的間距 當(dāng)gap > 1或swaps = 1時執(zhí)行回圈//代表未完成排序 gap =取「gap除以遞減率」的整數(shù)值//更新間距 swaps = 0 //用以檢查陣列是否已在遞增形式，只限gap=1時有效 //把輸入陣列「梳」一次 i = 0到(array的長度- 1 - gap)來執(zhí)行回圈//從首到尾掃描一次；因?yàn)殛嚵性氐木幪枏?開始，所以最后一個元素編號為長度-1 如果array[i] > array[i+gap] 把a(bǔ)rray[i]和array[i+gap]的數(shù)值交換 swaps = 1 //曾作交換，故此陣列未必排序好 如果結(jié)束 回圈結(jié)束 回圈結(jié)束程序結(jié)束算法實(shí)現(xiàn)C語言實(shí)現(xiàn)：2

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 data[i + delta]){data[i] ^= data[i + delta];data[i + delta] ^= data[i];data[i] ^= data[i + delta];noswap = 0;}if(delta > 1){delta /= shrink;noswap = 0;}}}動作原理假設(shè)輸入為

8 4 3 7 6 5 2 1

目標(biāo)為將之變成遞增排序。因?yàn)檩斎腴L度=8，開始時設(shè)置間距為8/1.3≒6，則比較8和2、4和1，并作交換兩次。

84 3 7 6 521

243 7 6 5 81

2 1 3 7 6 5 8 4

第二次循環(huán)，更新間距為6/1.3≒4。比較2和6、1和5，直至7和4，此循環(huán)中只須交換一次。

2 1 376 5 84

2 1 3 4 6 5 8 7

接下來的每次循環(huán)，間距依次遞減為3 → 2 → 1，

間距=3時，不須交換

2 1 3 4 6 5 8 7

間距=2時，不須交換

2 1 3 4 6 5 8 7

間距h=1時，交換三次

2****13 4 6 5 8 7

1 2 3 46****58 7

1 2 3 4 5 68****7

1 2 3 4 5 6 7 8

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

參看泡沫排序，梳排序的基本，較慢的算法。

雞尾酒排序，或雙向泡沫排序，一樣解決了泡沫排序中的烏龜問題。

本詞條內(nèi)容貢獻(xiàn)者為:

李岳陽 - 副教授 - 江南大學(xué)