Comb Sort（梳排序，梳子排序）

首先说明该排序算法是抄*的

http://zh.wikipedia.org/zh-cn/%E6%A2%B3%E6%8E%92%E5%BA%8F

 

梳排序(Comb sort)是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自泡沫排序和快速排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成泡沫排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响泡沫排序的效能。

在泡沫排序中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入阵列大致排序好，并以泡沫排序作最后检查及修正。

 

注：阵列也就是数组了，是港台那边的术语。

 

算法还是很简单的，直接给出源代码：

 

#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAX_LENGTH 10void swap(int *a, int *b) { int t = *a; *a = *b; *b = t;}void print_array(int *a, int n) { int i; for ( i = 0; i < MAX_LENGTH; i++ ) { printf("%d ", a[i]); } printf("/n/n");}void shuffle(int *a, int n) { srand((unsigned int)time(NULL)); int i; for ( i = n - 1; i > 0; i-- ) { int s = rand() % (i + 1); swap(&a[s], &a[i]); }}void combsort(int *a, int n) { float factor = 1.3; int r = 0; int g = n; int swapped = 1; while ( g > 1 || swapped ) { g = ( g > 1 ) ? g / factor : g; swapped = 0; int i = 0; while ( g + i < n ) { if ( a[i] > a[g+i] ) { printf("round %d, gap = %d, a[%d] <--> a[%d] // %d <--> %d:/n", r++, g, i, g+i, a[i], a[g+i]); swap(&a[i], &a[g+i]); swapped = 1; print_array(a, n); } i++; } }}int main(void) { int a[MAX_LENGTH]; int i; for ( i = 0; i < MAX_LENGTH; i++ ) { a[i] = i; } shuffle(a, MAX_LENGTH); printf("before sorting:/n"); print_array(a, MAX_LENGTH); combsort(a, MAX_LENGTH); printf("after sorting:/n"); print_array(a, MAX_LENGTH); return 0;}

 

执行过程和结果如下，测试用例生成的随机数组大约进行10次左右的交换就能够完成排序了：