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

今天药忘吃喽~ 2022-05-21 11:30 169阅读 0赞

## 桶排序 ##

假设我们要对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);
    }