基数排序（桶排序）

博主是一个大一刚刚放暑假的大学生，大学我们只学习了c语言，现在这么卷只学c语言肯定不够，所以博主打算从零开始恶补c++顺便写文章记录一下，另外博主这个暑假还想记录一些算法基础内容欢迎关注哦。这些是是一些算法的记录和整理总结笔记要是什么时候忘记了这个算法那个算法怎么做就重新来看看，在csdn上面发是为了利用网址来编写思维导图的话比! 较方便~~~如果大家想跟着我一起学习也可以关注我~或者给这个文章点赞~~~谢谢大家了~

• 桶排序
• • • 前言：
    • 基数排序（桶排序）思路：
    • 桶排序代码：

我们之前学过的排序都是基于比较的排序但桶排序是一个不基于比较的排序
**不基于比较的排序：**无法通过比较来判断大小要根据数据状况定制的是一类很小众的算法

1.看最大的有几位，把数组的数补成相同的位数
2.准备几个桶（把所有要出现的数字都当做桶）
3.从个位开始把每位数字放进桶里
4.把桶从左向右把所有的数字都倒出来（先进桶的先出桶）
5.十位数字重复3.4步。
6.百位数字重复3.4步。
7.最后全部重复完了就可以发现数字神奇的排好了!!!
因为我们是从个位开始排的一直到最高位所以数字可以从低到高排序
注意如果是桶排序的话必须有进制

解析都在代码里哦！一看就懂，这里的重点是运用了一个分片的思想

#include
#include
using namespace std;
//桶排序
int getdigit (int x, int d);
int getdigit (int x, int d){

    return ((x /((int) pow(10, d - 1))) % 10);//利用数学方法求位上的数
}
void radixsort (int* a, int L, int R, int digit);
void radixsort (int* a , int L, int R, int digit){//L.R表示一个范围digit表示最大的值有几个十进制位
    const int radix = 10;
    int i = 0, j = 0;
    //准备多少桶
    int b1[R - L + 1];
    for (int d = 1; d <= digit; d++ ){//需要发生多少次入桶出桶, d代表位数
        int count1[radix] = {0};//创造一个词频数组

        for (i = L; i <= R; i++)
            {
                j = getdigit(a[i], d);//调用函数获得这个位置上的数
                count1[j]++;//统计词频
            }
        for (i = 1; i < radix; i++)
        {
            count1[i]= count1[i] + count1[i - 1];

        } //分片

        j = 0;
        for (i = R; i >= L; i--)//从右向左遍历就是后入桶的先出来
        {
            j = getdigit(a[i], d);//看看这个数是什么看看词频
            b1[count1[j] - 1] = a[i];//词频-1就是他在这个片上的应该的位置
            count1[j]--;//这个片上有一个归位了那么剩余的就要减1
        }
        j = 0;
        for(i = L; i <= R; i++){
           a[i] = b1[j];把辅助数组里面存的数据给我们的数组
            j++;
        }
    }
}

int maxbits (int* a, int arr_len);//求最大位数
int maxbits (int* a, int arr_len)
{
    int max=a[0];
    for( int i = 1; i < arr_len; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }
    int con = 0;
    while(max != 0)
    {
        max /= 10;
        con ++;
    }
    return con;
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0;i < n; i++) {
        cin >> a[i];
    }
    radixsort(a, 0, n-1, maxbits(a, n));
     for (int i = 0;i < n; i++) {
        cout << a[i] << ' ';
    }


}