首页 > *nix技术 > 梳子排序(Comb Sort)

梳子排序(Comb Sort)

2012年8月14日 发表评论 阅读评论 9,111 次浏览

所谓的排序就是将记录按排序码递增(或递减)的次序排列起来,形成新的有序序列。假设有n个记录的序列为{R1,R2,…Rn},其相应的排序码为{K1,K2,…,Kn},那么排序就是要将这n个记录序列从新排序为{R1’,R2’,…Rn’},使得各记录对应的排序码满足K1’ < K2’ < … < Kn’(递增)或K1’ > K2’ > … > Kn’(递减)。另外,在我们讨论算法时,一般就取只包含有排序码的记录序列(各记录以下直接称之为元素),这样可以将我们的重点集中在排序算法上。

包含n个元素的序列在未排好序之前,其各个元素所处位置到其实际位置(即该序列排好序之后)必定有个距离,如下图所示:

元素11离它实际所在排序位置距离为8,元素8离它实际所在排序位置距离为5,元素1离它实际所在排序位置距离为8,…,利用冒泡排序,这些元素每次只移动一个距离位置,因此如果遇到离实际所在位置距离很远的元素,这种情况下排序效率就变得很差。梳子排序(该算法由Stephen Lacey和Richard Box设计,并于1991年4月发表在Byte杂志上:A fast, easy sort)的改进就在于它能让元素做跳跃式的移动,因此能尽快的将元素移动到它实际所在位置,该算法思想(Shell排序也是基于这种思想,但是Shell排序是基于插入排序)简单,但其效率(O(nlogn))可与快速排序(Quicksort)媲美。

梳子排序设置的初始跳跃距离(initial gap)为待排序序列的长度除以收缩因子(shrink factor,简写为s.f,收缩因子一般取值为1.3),然后每循环排序一次就将跳跃距离进行一次收缩(gap = gap / s.f),当跳跃距离为1时则不再收缩,此时进行的排序就是冒泡排序,但是由于现在大部分元素都已有序,所以效率会很高,当在一趟冒泡排序中没有任何数据进行交换时则表示排序工作完成,否则要继续进行冒泡排序。

就像Shell排序一样,收缩因子对梳子排序效率的影响也很大,在该算法的设计者最初发表的文章中给出的建议是收缩因子取值1.3,但后来也有人提出改进使用1/(1-(1/e))=1.279604943109628或1/(1-1/exp((sqrt(5)+1)/2))=1.247330950103979等。
当我们给收缩因子取值为1.3时,那么只有三种可能(反证法可证)的结束gap序列:(9,6,4,3,2,1),(10,7,5,3,2,1)和(11,8,6,4,3,2,1),而只有最后一种gap序列能够很好的减少最后的冒泡排序(即gap=1时)次数,因此当收缩出来的gap等于9或10时就人为的将其设置为11,这种梳子排序的变种被称之为Combsort11。下图是利用Combsort11进行排序的实例:

使用实例,C代码(来之lighttpd源码):

// mod_dirlisting.c
/* simple combsort algorithm */
static void http_dirls_sort(dirls_entry_t **ent, int num) {
	int gap = num;		/* 初始值为待排序序列的长度除以收缩因子。*/
	int i, j;
	int swapped;
	dirls_entry_t *tmp;
	do {
		gap = (gap * 10) / 13;
		if (gap == 9 || gap == 10)	/* Combsort11变种算法。*/
			gap = 11;
		if (gap < 1)
			gap = 1;		/* 保证至少为1,用于冒泡排序。*/
		swapped = 0;
		for (i = 0; i < num - gap; i++) {
			j = i + gap;
            /* 文件(夹)名称字符串的按字典序比较。*/
			if (strcmp(DIRLIST_ENT_NAME(ent[i]), DIRLIST_ENT_NAME(ent[j])) > 
					0) {
				tmp = ent[i]; 		/* 交换。*/
				ent[i] = ent[j];
				ent[j] = tmp;
				swapped = 1;
			}
		}
	} while (gap > 1 || swapped);		/* 注意排序完成的结束条件。*/
}

转载请保留地址:http://www.lenky.info/archives/2012/08/1861http://lenky.info/?p=1861


备注:如无特殊说明,文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限,虽力求内容正确无误,但仍然难免出错,请勿见怪,如果可以则请留言告之,并欢迎来讨论。另外值得说明的是,Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享,特别是一些带有完全参考的文章,其后附带的链接内容也许更直接、更丰富,而我只是做了一下归纳&转述,在此也一并表示感谢。关于本站的所有技术文章,欢迎转载,但请遵从CC创作共享协议,而一些私人性质较强的心情随笔,建议不要转载。

法律:根据最新颁布的《信息网络传播权保护条例》,如果您认为本文章的任何内容侵犯了您的权利,请以Email或书面等方式告知,本站将及时删除相关内容或链接。

  1. wpdzyx
    2012年8月21日10:12 | #1

    你的这些图片是用什么工具画的.

  1. 本文目前尚无任何 trackbacks 和 pingbacks.