这篇再看看一个经典的排序,梳排序,为什么取名为梳,可能每个梳都有自己的gap吧,大梳子gap大一点,小梳子gap小一点。
上一篇我们看到鸡尾酒排序是在冒泡排序上做了一些优化,将单向的比较变成了双向,同样这里的梳排序也是在冒泡排序上做了一些优化。
冒泡排序上我们的选择是相邻的两个数做比较,就是他们的gap为1,其实梳排序提出了不同的观点,如果将这里的gap设置为一定的大小,
效率反而必gap=1要高效的多。
下面我们看看具体思想,梳排序有这样一个1.3的比率值,每趟比较完后,都会用这个1.3去递减gap,直到gap=1时变成冒泡排序,这种
算法比冒泡排序的效率要高效的多,时间复杂度为o(n2/2p) 这里的p为增量,是不是跟希尔排序有点点神似。。。
比如下面有一组数据: 初始化的gap=list.count/1.3, 然后用这个gap作为数组下标进行跨数字比较大小,前者大于后者则进行交换,
每一趟排序完成后都除以1.3, 最后一直除到gap=1

最后我们的数组就排序完毕了,下面看代码: