参考维基百科
梳排序是Wlodzimierz Dobosiewicz于1980年发明的不稳定排序算法。梳排序改良自冒泡排序和快速排序，主要目的是消除冒泡排序中因为尾部小数值（乌龟）造成的排序缓慢问题。
冒泡排序中，尾部小数值称为乌龟，会严重影响排序性能；而头部的大数值称为兔子，对性能没影响
在冒泡排序中，只比较阵列中的相邻两项，即比较的gap=1，梳排序提出此间距可以大于1。在梳排序中，开始时的gap设置为阵列的长度，并在会圈中以固定的比例递减，通常递减率设定为1.3。在一次回圈中，梳排序如同冒泡排序一样，把阵列从头到尾扫描一次，以比较并交换两项，不同的是两项间距不为1，如果递减至1，梳排序假定输入阵列大致已经排序好了，并以冒泡排序最最后的验证。
希尔排序由插入排序优化而来，其思想也是插入排序中gap可以不为1
代码实现
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;
}
}
}
过程举例
举例：待排序序列为｛8， 6， 5， 2， 1， 4， 3，7｝
第一次
初始increment = 8/1.3 =6。分为子序列｛8， 3｝｛6， 7｝｛5｝｛2｝｛1｝｛4｝进行一趟冒泡排序，得到｛3， 6， 5， 2， 1， 4， 8， 7｝
第二次
increment = 6/1.3 = 4。分为子序列｛3， 1｝｛6， 4｝｛5， 8｝｛2， 7｝进行一趟冒泡排序，得到｛1， 4， 5， 2， 3， 6， 8， 7｝
第三趟
increment = 4/1.3 = 3，分为子序列｛1， 2， 8｝｛4， 3， 7｝｛5， 6｝进行一趟冒泡排序，得到｛1， 3， 5， 2， 4， 6， 8， 7｝
第四趟
increment = 3/1.3 = 2。分为子序列｛1， 5， 4， 8｝｛3， 2， 6， 7｝进行一趟冒泡排序，得到｛1， 2， 4， 3， 5， 6， 8， 7｝
第五趟
increment = 2/1.3 = 1。分为子序列｛1， 2， 4， 3， 5， 6， 8， 7｝进行一趟冒泡排序，得到｛1， 2， 3， 4， 5， 6， 7， 8｝
算法分析
- 递减率的设定影响梳排序的效率，原作者以随机数实验，得到最有效的递减率为1.3
- 设定递减率为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
- 与快排和归并排序一样，刚开始是效率很好，结尾时效率较差，如果间距变得太小时如小于10，改用插入或希尔等算法，可以提升整体性能。
动态过程
comb_sort.gif
