算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

在前面的计数排序中,我们已经领略到了如何用空间换时间的方法,找到一种线性时间复杂度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)

One thought on “算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

Leave a Reply to 1 Cancel reply

Your email address will not be published. Required fields are marked *