数据结构-基数排序（桶排序）

逃离我推掉我的手 2022-06-03 02:28 186阅读 0赞

##### 基数排序和计数排序都属于“非比较排序”，有关计数排序可查看[http://blog.csdn.net/sssssuuuuu666/article/details/78677302][http_blog.csdn.net_sssssuuuuu666_article_details_78677302]。 #####

--------------------

> #### **基数排序介绍：** ####
> 
> ##### 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。按照排序的顺序会被分为：最高位优先法和最低位优先法。以下实现的是最低位优先法（LSD）。 #####
> 
> ##### 基数排序是稳定排序，所谓稳定不稳定是说序列中相同元素经过排序后,他们的先后顺序不变。 #####

--------------------

> #### **思路** ####
> 
> ##### 先按照最低位进行排序，接下来是次高位，一直到数据中最大的位数排序完。 #####
> 
> ##### 1、计算出数组中最大的数字是几位数；是几位数我们在接下来的排序中最外层就会循环几次； #####
> 
> ##### 2、开辟一个“桶”以及用来临时存放排序的数组；“桶”只开辟十个int大小，因为十进制下只有0-9十个数字，用来记录数据的某一位对应数字出现的次数，（例如，3,23，那么当个位数在进行排序时bucket\[3\] = 2）；另开辟一个n个元素的tmp数组，用来暂时存放排序的结果； #####
> 
> ##### 3、每次最外层循环开始时，先将bucket数组重新都置为0，计算出数组中所有元素对应位（例，个位，十位，百位）出现的个数，并同步到bucket数组中； #####
> 
> ##### 4、按照bucket数组中的顺序，将数据排序到tmp数组中； #####
> 
> ##### 5、redix\*=10，再进行下一轮的循环。 #####

--------------------

> #### **实现以及测试代码如下：** ####

#include <iostream>
    using namespace std;
    
    //求数组中最大数的位数
    int GetBitNum(int* arr, int n)
    {
        int maxBitNum = 1;
        int tmp = 10;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= tmp)
            {
                tmp *= 10;
                maxBitNum++;
            }
        }
        return maxBitNum;
    }
    
    void redix_sort(int* arr, int n)
    {
        int bit_num = GetBitNum(arr, n); 
        int* tmp = new int[n];
        //bucket为0-9的桶
        int* bucket = new int[10];
        int redix = 1;
        for (int i = 1; i <= bit_num; i++)
        {
            //先清空桶数据
            for (int i = 0; i < 10; i++)
                bucket[i] = 0;
    
            //统计每个桶中的数字个数
            for (int i = 0; i < n; i++)
            {
                    int index = (arr[i] / redix) % 10;
                    bucket[index]++;
            }
    
            //转换为下标，方便一会用
            for (int i = 1; i < 10; i++)
                bucket[i] = bucket[i - 1] + bucket[i];
    
            //重新排序数组
            for (int i = n - 1; i >= 0; i--)
            {
                int index = (arr[i] / redix) % 10;
                tmp[bucket[index] - 1] = arr[i];
                bucket[index]--;
            }
    
            //拷贝回原数组，进行下一轮排序
            for (int i = 0; i < n; i++)
                arr[i] = tmp[i];
    
            //准备下一位
            redix *= 10;
        }
    }
    
    
    int main()
    {
        int arr[] = { 73,2,93,43,55,14,28,6,39,81 };
        redix_sort(arr, sizeof(arr) / sizeof(arr[0]));
        for (int i = 0; i < 10; i++)
            cout << arr[i] << " ";
        cout << endl;
        system("pause");
        return 0;
    }
    
    //输出结果：2 6 14 28 39 43 55 73 81 93

--------------------

> ##### **图示基数排序过程：** #####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_sssssuuuuu666_article_details_78677302]: http://blog.csdn.net/sssssuuuuu666/article/details/78677302
[SouthEast]: /images/20220603/facaa673f13545098f1def2b9139933f.png