Lenky个人站点

所谓的排序就是将记录按排序码递增（或递减）的次序排列起来，形成新的有序序列。假设有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://lenky.info/archives/2012/08/14/1861 或 http://lenky.info/?p=1861

---

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

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