在前面的计数排序中，我们已经领略到了如何用空间换时间的方法，找到一种线性时间复杂度O(N)的排序算法。

计数排序的缺点也是非常明显的：一旦数据范围[0,k)，中的k]相对于数据量N非常稀疏，计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

个人认为：桶排序 = 哈希排序 = 散列排序，基本思想是一样的。

于是桶排序/哈希排序应运而生，假设值域范围还是k，我们不去创建k个buckets，而是创建m个木桶，让N个元素通过哈系函数映射到这k个桶即可。这里还有一个必须注意的大前提：哈希函数必须保证m个桶有序！即若i < j，则桶bi中的元素要小于桶bj中的元素。

一个这种哈希函数的例子，对0~1之间的浮点数映射到m个桶中

int hash(double *d, int m)
{
    int bucket = m*(*d);
    return bucket;
}

利用了C语言强制转换丢失精度的特性，非常巧妙吧！如此一来0.5的hash一定小于0.69！

哈希排序同时带来的问题是：一个桶中会含有多个元素，对这些元素的排序可以使用插入排序（在数据量小时，如n=4，插入排序是最快的。）

虽然插入排序的时间复杂读是O(N^2)，但是散列平均的话，可以证明对每个桶内进行插入排序，其时间消耗是常数！即总体的散列排序/哈希排序的时间复杂度仍然是O(N)!!

因此，对于散列排序而言，桶k的个数越大，排序速度就会不断加快。当选择足够多的桶个数时，散列排序可以比快速排序更快！

散列排序不止可以用于数值，还可用于随机字符的排列，以26个字母为例：
我们将字符串的前3位想乘做为一个Hash函数，那么k的空间毫无疑问是26^3

#桶数量计算
int numBuckets()
{
    return 26*26*26;
}

int hash(char* elem)
{
    return (elem[0] - 'a')*26*26 +
           (elem[1] - 'a')*26 +
           (elem[2] - 'a');
}

只有在桶很少的情况下，散列排序的性能会退化接近于O(N^2)