梳排序(Comb sort)是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序。

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

使用梳排序为一列数字进行排序的过程

本文地址：http://www.cnblogs.com/archimedes/p/comb-sort-algorithm.html，转载请注明源地址。

例：        88     7     79     64     55     98     48     52     4      13             

第一趟:    gap=10/1.24=8

比较数值对: (88, 4), (7, 13)

结果为：   4      7     79     64     55     98     48     52     88     13 

第二趟：   gap=8/1.24=6

比较数值对: (4, 48), (7, 52), (79, 88), (64, 13)

结果为：   4      7     79     13     55     98     48     52     88     64

第三趟：   gap=6/1.24=4

比较数值对: (4, 55), (7, 98), (79, 48)  交换后：4      7     48     13     55     98     79     52     88     64 

继续比较数值对：(13, 52), (55, 88), (98, 64)

结果为：   4      7     48     13     55     64     79     52     88     98

第四趟：   gap=4/1.24=3

比较数值对: (4, 13), (7, 55), (48, 64), (13, 79), (55, 52), (64, 88), (79, 98)

结果为：   4      7     48     13     52     64     79     55     88     98

第五趟：   gap=3/1.24=2

比较数值对: (4, 48), (7, 13), (48, 52), (13, 64), (52, 79), (64, 55), (79, 88), (55, 98),

结果为：   4      7     48     13     52     55     79     64     88     98

第六趟：   gap=2/1.24=1

比较数值对: (4, 7), (48, 13), (52, 55), (79, 64), (88, 98)

结果为：   4      7     13     48     52     55     64     79     88     98

算法实现：

// Completed on 2014.10.8 21:27// Language: C99//// 版权所有（C）codingwu   (mail: oskernel@126.com) // 博客地址：http://www.cnblogs.com/archimedes/#include<stdio.h>     #include<stdbool.h>  void swap(int *a, int *b)   //交换两元素的值{    int t;    t = *a;    *a = *b;    *b = t;}void printArray(int a[], int count)   //打印数组元素{    int i;    for(i = 0; i < count; i++)        printf("%d ",a[i]);    printf("\n");}void combsort(int *a, int size) {   float shrink_factor = 1.247330950103979;   //设置递减率  int gap = size, i;  bool swapped = true;   while ((gap > 1) || swapped) {  //当gap=1时，已经基本有序, swapped最后一次遍历排序    if (gap > 1) gap = gap / shrink_factor;    swapped = false;     i = 0;    while ((gap + i) < size) {      if (a[i] > a[i + gap]) {        swap(&a[i], &a[i + gap]);        swapped = true;      }      ++i;    }  }}int main(void)   {    int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1};    int n = sizeof(a) / sizeof(*a);    printArray(a, n);    combsort(a, n);    printArray(a, n);    return 0;}

梳排序算法