梳排序
梳排序(英語: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),改用插入排序或希爾排序等算法,可提昇整體效能。 此方法最大好處是不需要檢查是否進行過交換程序以將排序迴圈提早結束。 虛擬碼梳排序程序(以array作輸入) gap = array的長度 //設定開始時的間距 實作範例C語言void comb_sort(int arr[], int len) {
double shrink_factor = 0.8;
int gap = len, swapped = 1, i;
int temp;
while (gap > 1 || swapped) {
if (gap > 1)
gap *= shrink_factor;
swapped = 0;
for (i = 0; gap + i < len; i++)
if (arr[i] > arr[i + gap]) {
temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = 1;
}
}
}
C++template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void comb_sort(T arr[], int len) {
double shrink_factor = 0.8;
int gap = len, swapped = 1, i;
while (gap > 1 || swapped) {
if (gap > 1)
gap = (int) ((double) gap * shrink_factor);
swapped = 0;
for (i = 0; gap + i < len; i++)
if (arr[i] > arr[i + gap]) {
swap(arr[i], arr[i + gap]);
swapped = 1;
}
}
}
Javapublic 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 * 0.8);
}
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++;
}
}
}
JavaScriptArray.prototype.comb_sort = function() {
var shrink_factor = 0.8;
var gap = this.length, swapped = 1, i;
var temp;
while (gap > 1 || swapped) {
if (gap > 1)
gap = Math.floor(gap * shrink_factor);
swapped = 0;
for (i = 0; gap + i < this.length; i++)
if (this[i] > this[i + gap]) {
temp = this[i];
this[i] = this[i + gap];
this[i + gap] = temp;
swapped = 1;
}
}
return this;
};
PHPfunction swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}
function comb_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
$shrink_factor = 0.8;
$gap = count($arr);
$swapped = 1;
while ($gap > 1 || $swapped) {
if ($gap > 1)
$gap = floor($gap * $shrink_factor);
$swapped = 0;
for ($i = 0; $gap + $i < count($arr); $i++)
if ($arr[$i] > $arr[$i + $gap]) {
swap($arr[$i], $arr[$i + $gap]);
$swapped = 1;
}
}
}
Gofunc comb_sort(data sort.Interface) {
n := data.Len()
shrinkFactor := 0.8
gap := n
swapped := true
for gap > 1 || swapped {
if gap > 1 {
gap = int(float64(gap) * shrinkFactor)
}
// 冒泡排序
swapped = false
for i := 0; i < n - gap; i++ {
if data.Less(i + gap, i) {
data.Swap(i + gap, i)
swapped = true
}
}
}
}
# Julia Sample : CombSort
function CombSort(A)
gap,swapped = length(A),1
while (gap>1) || (swapped==1)
gap = floor(Int,gap/1.25)
swapped=0
for i=1:(length(A)-gap)
if A[i]>A[i+gap]
A[i],A[i+gap] = A[i+gap],A[i]
swapped=1
end
end
end
return A
end
# Main Code
A = [16,586,1,31,354,43,3]
println(A) # Original Array
println(CombSort(A)) # Comb Sort Array
動作原理假設輸入為
目標為將之變成遞增排序。因為輸入長度=8,開始時設定間距為8/1.3≒6,則比較8和2、4和1,並作交換兩次。
第二次迴圈,更新間距為6/1.3≒4。比較2和6、1和5,直至7和4,此迴圈中只須交換一次。
接下來的每次迴圈,間距依次遞減為3 → 2 → 1, 間距=3時,不須交換
間距=2時,不須交換
間距h=1時,交換三次
上例中,共作了六次交換以完成排序。 參考文獻參看外部連結維基教科書中的相關電子教程:Sorting/Comb sort |