一个快得出奇又慢得可以的比特排序算法

1.起因

提起排序算法，大家都能随意讲出一大堆，比如冒泡，Shell，插入，快排等...然而有没有想过自己实现一个排序算法。我曾经在前年的时候实现了一个本应该由GPU来执行的移位排序算法，可惜没有搞到硬件和软件，那篇文章是：(http://blog.csdn.net/dog250/article/details/5303538)《移位排序算法--从赛跑想到的》，该文用递推的方式实现了移位排序，代码冗长，很不清晰，如今我自己都懒得剖析了。同样基于赛跑的思想，本文实现了一个超级简洁的移位排序算法，效率嘛，快得出奇，又慢得可以！

2.思想

大家都知道赛跑，在跑道上每人一道，看谁先跑到终点谁就是冠军，然后看剩下的人中谁先跑到终点，此为亚军，然后季军，...一直到倒数第一。
实际上，计算机实现的排序非常符合这个思想，以往的传统算法为了排序，难免要在待排序数中做两两比较，何不用一个外部基准，一起上呢？这一点我觉得赛跑规则的发明真是一项创举，否则就需要比赛者两两比赛了，不把人累死才怪！相比之下诸如摔跤，相扑，拳击以及乒乓球等项目却都是两两比较的项目，然而两两比较也是讲策略的，比如分组赛，淘汰赛等，实际上传统的排序算法都是基于两两比较的算法，就是因为比赛策略不同，才出现不同的大O。
本文实现的排序算法不需要两两比较，完全基于外部的基准来进行，特别容易利用硬件特性来并行实现。那么外部基准是什么呢？我想起刘翔的110米栏，每撞栏一次就会减速一次，结果撞栏最少的获胜的可能性最大(当然还有别的因素，状态，实力，运气...)，所有待排序的数字都是同一类型，同一类型数据拥有同一宽度，比如32系统int型就是32位，char型一般8位，把数据的宽度作为栏杆，那么对于int类型，所有的待排序数据就都要跨过32个栏杆了，如果某个栏杆处某个数据对应的位是1，那么就表示跨过了该栏杆，若是0，则表示撞到了该栏杆，需要减速，本质上，算法逻辑需要判别一个指标，那就是“谁跑得远”而不是谁先到终点，第4节会说明为何这么做。

3.代码与效率

3.1.版本一：使用Integer

该版本使用Integer是因为在Eclipse中可以自动补全方法，写起来比较方便。用这种方法快速完成一个能跑的程序

public class CLSBitSort {
    static ArrayList<Integer> list = new ArrayList(0);
    static void BitSort(ArrayList<Integer> a, int base) {
        if (a.size() == 1) {
                        CLSBitSort.list.add(a.get(0));
                } else {
                        int i = 0;
                        ArrayList<Integer> one = new ArrayList(0);
                        ArrayList<Integer> zero = new ArrayList(0);
                        for (i = 0; i < a.size(); i++) {
                //给出一个基准，所有的数据的某一位都在此和base逻辑与，判定是否撞栏
                                if ((a.get(i).intValue()&base) == base)
                                        one.add(a.get(i));
                                else
                                        zero.add(a.get(i));
                        }
                        if (base > 0) {
                                if (one.size() > 0)
                                        CLSBitSort.BitSort(one, (base>>1));
                                if (zero.size() > 0)
                                        CLSBitSort.BitSort(zero, (base>>1));
                        }
                        if (base == 0) {
                                for (i = 0; i < a.size(); i++) {
                                        CLSBitSort.list.add(a.get(i));
                                }
                        }
                }
        }
        public static void main(String arg[]) {
                int base = 0x200;
                ArrayList<Integer> all = new ArrayList(0);
                for (int i = 0; i < 1500000; i++) {
                        Random random =new java.util.Random();
                        int v = random.nextInt(1000);
                        all.add(new Integer(v));
                }
                CLSBitSort.BitSort(all, base);
        for (int i = 0; i < CLSBitSort.list.size(); i++) {
        //    System.out.println(CLSBitSort.list.get(i));
        }
        }
}

用同样的方法写出冒泡，插入，快排等算法，在Linux下用time命令测试，比特排序算法在大量数据情况下效率明显高很多，有时虽然略逊快排一筹，然则直追之，不幸的是，使用了递归，又大量使用对象，空间复杂度极高。

3.2.版本二：使用int数组

使用数组是最直接的，因为版本一并不能证明比特移位排序是最快的，原因是我们不知道ArrayList的add以及set方法内部做了什么，有可能set方法是瓶颈呢...因此版本二不使用对象，而是直接使用int数组来完成排序：

static int result[] = new int[3500];
static int index = 0;
static void BitSort(int a[], int base, int size) {
    if (size == 1) {
        result[index++] = a[0];
    } else {
        int i = 0, one_size = 0, zero_size = 0;
        int one[] = new int[size];
        int zero[] = new int[size];
        for (i = 0; i < size; i++) {
            if ((a[i]&base) == base)
                one[one_size++] = a[i];
            else
                zero[zero_size++] = a[i];
        }
        if (base > 0) {
            if (one_size > 0)
                BitSort(one, (base>>1), one_size);
            if (zero_size > 0)
                BitSort(zero, (base>>1), zero_size);
        }
        if (base == 0) {
            for (i = 0; i < size; i++) {
                result[index++] = a[i];
            }
        }
    }
}

用这个版本测试下来，发现该算法总是比不过快排，因此着手优化之，本来脑子里面的算法很完美，结果写出来还是很丑陋，这是仓促的结果，因此必须有版本三

3.3.优化版本二

该版本讲逻辑判断优化掉，理由很简单，因为判断涉及到跳转，进而涉及分支预测，而分支预测一旦失败的代价极高！

import java.util.*;
public class CLSBitSort {
        static int result[] = new int[3500000];
        static int index = 0;
        static void BitSort(int a[], int base, int size) {
                if (size == 1 || base == 0) {  //用||增加了进入该分支的几率，同时减少一次预测
                        for (int i = 0; i < size; i++) {
                                result[index++] = a[i];
                        }
                } else {
                        int one_size = 0, zero_size = 0;
                        int one[] = new int[size];
                        int zero[] = new int[size];
                        for (int i = 0; i < size; i++) {
                                if ((a[i]&base) == base)
                                        one[one_size++] = a[i];
                                else
                                        zero[zero_size++] = a[i];
                        }
                        if (one_size > 0)
                                BitSort(one, (base>>1), one_size);
                        if (zero_size > 0)
                                BitSort(zero, (base>>1), zero_size);
                }
        }
        public static void main(String arg[]) {
                int base = 0x1000;
                int all[] = new int[3500000];
                for (int i = 0; i < 3500000; i++) {
                        Random random =new java.util.Random();
                        int v = random.nextInt(4000);
                        all[i] = v;
                }
                CLSBitSort.BitSort(all, base, 3500000);
                                for (int i = 0; i < 3500000; i++) {
                                        //System.out.println(result[i]);
                                }
        }
}

测试下来发现，BitSort无疑是最快的。
空间换时间，在内存不值钱的今天这无疑是一剂猛药，然而算法开发的成本也极高，一个月一个程序员少说也有4位数，这一个个一组组的4位大洋数交给一个没有任何立杆见影产出的所谓算法，在国内实属玩物丧志...

4.实质

为何不测谁先到终点呢？因为基于时间的测试在计算机的同一个程序中很难进行，因为冯诺依曼机器就是在时间轴上顺序执行的。那么就要采用一个变通的测试。先到终点的肯定在某一个时刻跑得最远。在这个算法执行的比赛中，是不能存在超越的。如果为待比较元素都维护一个计数器来表示“谁跑的远”这项测试指标的话，最终我们还需要来比较这些计数器的大小，这又回到了最终的问题，那就是排序！好在我们可以充分使用计算机的知识，在这个例子里，递归调用恰好为我们完成“看谁跑的远”这个测试，最终这项指标就落实在了看谁的递归调用深度最深这个指标。
我们完全信任递归，实质上，递归是一个“按照一定的顺序来执行自身”的算法，这个“一定的顺序”就是我们需要实现的逻辑，也就是程序的逻辑！大多数情况下，我们只关心递归的调用逻辑，殊不知递归其本身也可以被利用，这就是本例排序算法的本质！

5.感言

这个程序有很多缺点，但是其最大的优点我觉得是它非常简单，仅仅几行就能搞定完全的排序操作。在效率上，由于消除了两两比较和交换操作，更有效的利用了局部性原理，提高了cache的利用率，这也许为它能胜出绝大多数竞赛加了分。消除交换是很有意义的，因为消除了频繁交换，也就消除大量的cache失效，因此会些许提升些效率。