# 梳排序

分類 使用梳排序為一列数字进行排序的过程 排序算法 陣列 $\Omega(n^2)$[1] $O(n)$ $\Omega(n^2/2^p)$ 其中p表示增量 (the number of increments)[1] $O(1)$

## 算法實現

### 算法

梳排序程序(以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);

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


### javascript語言

function combSort(list){
var len = list.length;
var gap = len;
var swapped = true;

while(gap > 1 || swapped){
if(gap > 1){
gap = Math.floor(gap / 1.3); //获取排序间隔
}

var i = 0;
swapped = false;
while(i + gap < len){
if(list[i] - list[i + gap] > 0){ //如果为正数,交换位置
var tmp = list[i];
list[i] = list[i + gap];
list[i + gap] = tmp;
swapped = true;
}
i++;
}
}

return list;
}


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

## 參看

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