Bit Sort

介绍一个时间和空间复杂度都比较合理的排序方式 - 位排序

不同于堆排、快排、融合排序，位排序的思想简单粗暴。假设对一组不重复且属于[0, 10000000)区间的数A进行排序，初始化一个长度为10000000的数组，所有成员值默认为0，然后遍历A，假如存在，就在数组对应的index上修改为1；最后遍历数组，去掉为0的成员，并将值为1的成员值替换成对应index，排序就完成了。不过这样操作有个缺点，空间复杂度过高，所以就有了位排序。

总体思想，将[0, 10000000)切分成 10000000/32+1 个成员，以二进制来表示对应index的数存在与否

// 初始化成员
top := int(len(list)/BITSPERWORD) + 1
a := make([]uint, top)

for i := 0; i < top; i++ {
    a[i] = 0
}

那怎么来分配某个数属于那个一成员里面呢，其实很简单，因为每个slot有32个成员，那直接num除以32取整就可以了，举个例子：129//32 = 4，即129应该放入第四个成员中；第二步，数怎么在成员中表示呢，也很简单，num除以32取余数，即num%32，最后一步，加起来，至于为什么是加起来，请自行思考。表述比较啰嗦，代码其实就一行。

a[member>>SHIFT] |= 1 << (member & MASK)

全部代码

func bitsort(list []uint, max uint) []uint {
    var SHIFT, MASK uint = 5, 0x1f
    var BITSPERWORD int = 32
    top := int(len(list)/BITSPERWORD) + 1

    a := make([]uint, top)
    for i := 0; i < top; i++ {
        a[i] = 0
    }

    for _, member := range list {
        a[member>>SHIFT] |= 1 << (member & MASK)
    }

    var slot int = 0
    for i := uint(0); i < max; i++ {
        if a[i>>SHIFT]&(uint(1)<<(i&MASK)) != 0 {
            list[slot] = i
            slot++
        }
    }
    return list
}