排序算法四:梳排序

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
606
文章
12
评论
2020年2月7日16:28:56 评论

一、梳排序简介

梳排序是冒泡排序的一种优化方案,主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据,先进行部分优化,然后逐步减少步长,以此来对数据进行预处理。

以数组[3,1 5, 2, 4]为例,假设步长是2,那么就分别处理[3, 5, 4]和[1, 2],先局部优化。优化完成后,再使用冒泡排序。

关于步长的选取

步长并不是逐步递减的,步长的选取一般通过一个步长因子来控制:

  1. 初始化时,步长等于数组长度除以步长因子。
  2. 后续的所有步长都等于前一次步长除以步长因子,直到步长小于等于1。

从实验结果来看,这个步长因子设置为1.3时能获得较好的性能,并且实验数据证明,梳排序的良好性能甚至可以与快速排序媲美。

排序示例

以数组[41, 11, 18, 7, 16, 25, 4, 23, 32, 31, 22, 9, 1, 22, 3, 7, 31, 6, 10]为例,它的长度是19,计算得到的步长分别是[14, 10, 7, 5, 3, 2],它的预处理过程可以整理为:

排序算法四:梳排序

其中no表示第几趟排序,step表示步长,data是当前经过处理后的数组。很明显可以看出经过6次预处理后,数据已经基本有序了。

此时再通过冒泡排序来对整体排序就能减少很多工作量了(实际上只需要再做一次冒泡排序就能完成排序了)。如果没有第一阶段的处理,冒泡需要19趟排序才能完成,而经过处理后,第8趟排序就已经有序了。此时排序结束,节省了一半以上的时间。

二、代码

C++代码:

马谦马谦马谦
  • 本文由 发表于 2020年2月7日16:28:56
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/comb_sort.html
排序算法五:堆排序 数据结构和算法

排序算法五:堆排序

一、堆排序原理 通过最大堆的性质可以知道:一个堆中最大的元素总是在堆顶的,即数组下标0的位置。基于这一点,我们可以每次都把堆中的最大值提取出来,放到当前数组的后面。然后重新构建最大堆,重复这个过程,以...
排序算法七:计数排序 数据结构和算法

排序算法七:计数排序

一、计数排序 其基本思想为:假设n个输入的元素中的每一个都是在0到k之间的一个整数,对于每一个输入元素x,确定小于x的元素个数,直接把x放在它输出的数组中的位置上。例如有17个元素小于x,则x就应该在...
排序算法三:冒泡排序 数据结构和算法

排序算法三:冒泡排序

一、原理 冒泡排序的原理很简单, 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从从Z到A)错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。 冒泡排序不管在什...
排序算法二:选择排序 数据结构和算法

排序算法二:选择排序

一、原理 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: