易语言梳排序

在泡沫排序中,只比较阵列中相邻的二项,即比较的二项的间距(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,改用插入或希尔等算法,可以提升整体性能。

动画演示

511遇见

梳排序易语言源码:

.版本 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
.否则
.如果结束
.判断循环尾 ()
.判断循环尾 ()


发布日期:

所属分类: 易语言 标签: