梳排序又称梳子排序（Comb sort）是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，是不稳定排序算法。梳排序是改良自泡沫排序和快速排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成泡沫排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响泡沫排序的效能。

在泡沫排序中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至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、递减率的设定影响梳排序的效率，原作者以随机数实验，得到最有效的递减率为1.3
2、设定递减率为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，3、则到间距编程1时，数值通常不是递增数列，故因此要经过几次冒泡修正。这种假如指定间距的变异算法称为梳排序-11
4、与快排和归并排序一样，刚开始是效率很好，结尾时效率较差，如果间距变得太小时如小于10，改用插入或希尔等算法，可以提升整体性能。

动画演示

梳排序易语言源码：

.版本 2

.子程序 Combsort, , , Combsort
.参数 array, 整数型, 数组
.局部变量 gap, 整数型
.局部变量 i, 整数型
.局部变量 t, 整数型
.局部变量 swapped, 整数型
.局部变量 shrink_factor, 双精度小数型
.局部变量 intsize, 整数型
.局部变量 temp, 整数型

t ＝ 取数组成员数 (array)
.如果真 (t ≤ 0)
返回 ()
.如果真结束
shrink_factor ＝ 1.247330950104
gap ＝ t
swapped ＝ 1
.判断循环首 (gap ＞ 1 或 swapped ＝ 1)
.如果真 (gap ＞ 1)
gap ＝ gap ＼ shrink_factor
.如果真结束
swapped ＝ 0
i ＝ 0
.判断循环首 (gap ＋ i ＜ t)
i ＝ i ＋ 1
.如果 (array [i] － array [i ＋ gap] ＞ 0)
temp ＝ array [i]
array [i] ＝ array [i ＋ gap]
array [i ＋ gap] ＝ temp
swapped ＝ 1
.否则
.如果结束
.判断循环尾 ()
.判断循环尾 ()