【算法】桶排序和基数排序

桶排序

假设我们要对n个整数排序，而且这n个数的大小在区间[0,m]之内。那么我们可以设置m+1个”桶”来表示区间内的m+1个数，用数组bucket[m+1]表示。然后遍历n个待排数据，将每个数字放入到它对应的”桶”中。最后我们按照”桶号”递增的顺序将n个数字一次从”桶”中取出，那么取出的数字序列就是排序后的序列了。
桶排序使用了hash的思想，将n个数散列在了m个”桶”中，然后利用桶固有的顺序将数据取出，从而使得待排数据有序。这种方法避免了通过比较数据大小来排序，时间复杂度降到了O(n+m)。是一种典型的空间换时间的算法。

代码

//参数n表示待排数据的范围内数字的个数
//bucket[i]的值表示i号桶中重复数据的个数
//如果待排数组的范围不是从0开始的,而是区间[l,r]
//可以在排序前将所有数据减去l，排序后再加回来
void bucket_sort(vector<int> &A, int n)
{
    vector<int> bucket(n, 0);

    for(int i = 0; i < A.size(); i++){
        bucket[A[i]]++;
    }

    for(int i = 0, j = 0; i < n; i++){
        for(int k = 0; k < bucket[i]; k++)
            A[j+k] = i;
        j += bucket[i];
    }
}

基数排序

基数排序是在桶排序上的改进，能够节约很多空间。它的思想是这样的：对于待排序的整数序列，从整数的低位开始，依次对该位进行桶排序，直到排完最高位，所得的序列即是有序的。

代码

//这里的n表示整数的位，从0开始，依次表示个位，十位，百位。。。
void bucket_sort(vector<int> &A, int n)
{
    vector<vector<int> > buckets(10);

    //将数字第n位的数作为索引，将数字存入对应的桶中
    for(int i = 0; i < A.size(); i++){
        buckets[(A[i] / (int)pow(10,n))%10].push_back(A[i]);
    }
    //将数字依次从桶中取出，放回到原来的数组
    for(int i = 0, j = 0; i < 10; i++){
        for(int k = 0; k < buckets[i].size(); k++)
            A[j+k] = buckets[i][k];
        j += buckets[i].size();
    }
}

//这里的n表示待排数据中的最高位
void radix_sort(vector<int> &A, int n)
{
    for(int i = 0; i < n; i++)
        bucket_sort(A, i);
}