一种特殊的排序算法 I

一种特殊的排序算法 I

     -- 位排序 OR 桶排序

---

绝大部分经典的排序算法，都是以元素间的比较为基础，如冒泡，选择，插入，快速，归并，堆排序等，虽然这些排序算法的时间和空间复杂度存在不同，但其算法平均时间复杂度均不超过O(n logn) （基数排序也比较特殊可做到O(k*n)），详细对比情况可以参见维基排序算法。

===

而下面内容描述的排序算法比较特殊，并非以元素间比较为基础的，其算法时间复杂度达到了O(n)。先来看看一道简单的示例题目吧（引用自：Google groups TopLanguage）。

   
特殊排序算法题目，如下：
     姓名集合names，名次集合ranks，按照名次顺序输出她们的名字，要求O(N)的时间复杂度。

解法如下： 
     解法一，不改变原来集合顺序，O(N)时间， O(N)空间。
     描述： 数组下标相当于姓名索引，新空间以名次顺序依次记录着姓名索引。

     解法二，在位重新排序，改变原来集合顺序，O(N)时间， O(1)空间。
     描述：每一次swap确定一元素的位置，最多总共N次swap能全部定位。

具体的程序设计（C/C++）代码在这里。

===

有一种特殊的排序算法，在《编程珠玑I II》有讲述到的位排序(bitsort)，也称桶排序。

其实，上面的排序题目正是位排序的一种变种的应用，不知你是否已经发现了否？

位排序算法的整体思想，可以描述如下：
     1. 每字节有8bit（位），那么它就可标记8个连续的数，分别对应每bit位，若数值存在则对应bit位置为1。
     2. 把N个数分为1+N/8组(相当于有这么多个桶)，每组标记连续的8个数。

     3. 申请（1+N/8）字节数组均初始化为0，遍历要排序的集合，存在的元素在对应的bit位标记1。

     标记规则： array[i/8] = (array[i/8] | (1<<(i%8)))

注：算法描述的字节亦可替换为整型类型，对应的比特位数字变为32。

===

关于位排序，同样可以瞄瞄其他网友描述，这里。

后续想找时间再写一篇《一种特殊的排序算法 II》（20120629更新链接），关于计数排序☺。

（完）