# 梳排序

(the number of increments)[1]

## 虛擬碼

梳排序程序（以array作輸入）
gap = array的長度 //設定開始時的間距

當gap > 1或swaps = 1時執行迴圈 //代表未完成排序
gap = 取「gap除以遞減率」的整數值 //更新間距

swaps = 0 //用以檢查陣列是否已在遞增形式，只限gap=1時有效

//把輸入陣列「梳」一次
i = 0 到 (array的長度 - 1 - gap)來執行迴圈 //從首到尾掃描一次；因為陣列元素的編號從0開始，所以最後一個元素編號為長度-1
如果array[i] > array[i+gap]
把array[i]和array[i+gap]的數值交換
swaps = 1 //曾作交換，故此陣列未必排序好
如果結束
迴圈結束
迴圈結束



## 實作範例

### 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;
}
}
}


### 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 * 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++;
}
}
}


### JavaScript

Array.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;
};


### PHP

function 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;
}
}
}


### Go

func 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
}
}
}
}


8 4 3 7 6 5 2 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

2 1 3 7 6 5 8 4
2 1 3 4 6 5 8 7

2 1 3 4 6 5 8 7

2 1 3 4 6 5 8 7

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

## 參看

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