计数排序(Counting Sort)与比特计数排序(Bit Counting Sort)

前两篇介绍的梳排序和gnome排序，都是属于比较排序算法里面的交换排序方法。而计数排序是一种非比较排序算法，其C代码如下：

void countingsort(int *a, int n) {
    int i, min, max;
    min = max = a[0];
    for( i = 1; i < n; i++ ) {
        min = (a[i] < min) ? a[i] : min;
        max = (a[i] > max) ? a[i] : max;
    }
    int range = max - min + 1;
    int *count = malloc(range * sizeof(int));
    for( i = 0; i < range; i++ )
        count[i] = 0;
    for( i = 0; i < n; i++ )
        count[ a[i] - min ]++;
    int j, z = 0;
    for( i = min; i <= max; i++ )
        for( j = 0; j < count[ i - min ]; j++ )
            a[z++] = i;
    free(count);
}

计数排序的时间复杂度是O(n + k)，其中k代表该数组元素的取值范围。当数组中的所有元素均相差不大，最多互为线性关系时，计数排序的时间复杂度可以化为O(n)，在此情况下，计数排序的速度快于任何比较排序算法。

但是，计数排序也很有局限性。首先，只能排序整数，不能对浮点数和字符串进行排序；其次，需要额外的存储空间，该算法需要为每一个最小值到最小值加k之间的数，不管这个数在原数组中存在还是不存在，都要统计它在原数组中出现的次数，所以，当k比较大时，可能也是一笔不容忽视的开销。

本文的比特计数排序，正是为解决额外的存储空间问题而提出的。（注，写本文时并没有参考其它博客、资料或文献，不清楚该算法是否有更合适的名字，所以就按个人的理解命名为比特计数排序）

在不少情况下，我们只关心需要排序的键值，作为一个主键，有没有出现，不关心它出现了几次。这时候，如果使用一个整型变量来表示一个数组元素有没有出现，就有点浪费了。事实上，这仅仅需要一个比特，就可以做到：用1代表约定的元素有出现，0代表约定的元素没有出现。那么，一个无符号整数，在32位操作系统下，就可以对应普通计数排序里的32个count数组的元素。也就是说，比特计数排序仅需要普通计数排序所必须的额外存储空间的1/32，即可工作。

该算法如下：

#define BITS_NUM 32
void bitcountingsort(int *a, int n) {
    int i, j, k, min, max;
    min = max = a[0];
    for ( i = 1; i < n; i++ ) {
        min = (a[i] < min) ? a[i] : min;
        max = (a[i] > max) ? a[i] : max;
    }
    int range = max - min + 1;
    unsigned int *count = malloc((range / BITS_NUM + 1) * sizeof(unsigned int));
    for ( i = 0; i < range / BITS_NUM + 1; i++ )
        count[i] = 0;
    for ( i = 0; i < n; i++ ) {
        int q = (a[i] - min) / BITS_NUM;
        int r = (a[i] - min) % BITS_NUM;
        count[q] |= 0x01 << r;
    }
    for ( i = 0, j = 0; i < range / BITS_NUM + 1; i++ ) {
        k = 0;
        unsigned int c = count[i];
        while ( c ) {
            if ( c & 0x01 ) {
                a[j++] = min + i * BITS_NUM + k;
            }
            c = c >> 1;
            k++;
        }
    }
    free(count);
}

算法的前半部分，比特计数排序与普通计数排序是基本一样的，不外乎找出最大和最小的元素，分配count数组的空间并对其进行初始化，等等。后半部分，比特计数排序遍历count数组的次数比普通计数排序少，但是每次遍历的逻辑处理相对复杂，需要对每个位进行统计。实验证明，比特计数排序的效率与普通计数排序差不多。在我的电脑上，分别对一个4K大小的整型数组执行10000次洗牌和排序，多次执行，两者的运行时间都是4秒多。

此外，我曾经尝试使用移位和位运算代替算法中的整除和取模运算，以为能够大大提升执行速度，但是，事与愿违，这样修改后并没有带来任何性能上的提升。看来，现在的编译器早就对此进行了一定的优化，不必程序员操心了。

无可否认，比特计数排序同样有很大局限性：第一，还是只能对整数排序；第二，还是需要不少的额外存储空间，尽管占用的空间已经大大减少；第三，会去掉重复的元素。不过，寸有所长，尺有所短，在我看来，比特计数排序恰恰能满足那些要求去掉重复键值，或者键值已经是唯一值的场合。