基数排序代码实现

详情请看排序总结，传送门：https://blog.csdn.net/m0_52711790/article/details/121914543

基数排序的知识点我就不贴出来，相信都能搜到对应概念解释，下面就直接上代码，代码解释其实也很清晰了。

#include<iostream>
using namespace std;
 
///补充：(arr[i] / exp) % 10  这个表达式很重要哦，作用是截取到某个数的某一位
 
/// 获取数组arr中最大值，arr——待排序的数组，len——数组arr的长度。
int arrmax(int *arr, int len) {
    int i, imax;
    imax = arr[0];
    for (i = 1; i < len; i++)
        if (arr[i] > imax)
            imax = arr[i];
    return imax;
}
 
/// 对数组arr按指数位进行排序。
/// arr——待排序的数组，len——数组arr的长度。
/// exp——排序指数，exp=1：按个位排序；exp=10：按十位排序；......
void _radixsort(int *arr, int len, int exp) {
    int i;
    int result[len];       /// 存放从桶中排序好收集到的数据的临时数组。
    int buckets[10] = {0};   /// 初始化10个桶。
 
    ///遍历arr，将数据出现的次数存储在buckets中。
    for (i = 0; i < len; i++)
        buckets[(arr[i] / exp) % 10]++;
 
    ///调整buckets各元素的值，调整后的值就是arr中元素在result中的位置。
    ///核心是下面两行代码，我暂时不知道怎么解释。下面两行代码处理完后buckets的数字
    ///代表的是该桶前面有多少个已经排好序的数
    for (i = 1; i < 10; i++)
        buckets[i] = buckets[i] + buckets[i - 1];
 
    /// 将arr中的元素填充到result中。注意：一定得是倒序从后面一个一个读取哦！
    ///再说一遍，这里的倒序取非常关键！
    for (i = len - 1; i >= 0; i--) {
        int iexp = (arr[i] / exp) % 10;
        result[buckets[iexp] - 1] = arr[i];
        buckets[iexp]--;
    }
 
    /// 将排序好的数组result复制到数组arr中。
    ///memcpy(arr, result, len * sizeof(int));
    for (int i = 0; i < len; i++)
        arr[i] = result[i];
}
 
/// 基数排序主函数，arr——待排序的数组，len——数组arr的长度。
void radixsort(int *arr, int len) {
    int imax = arrmax(arr, len);    /// 获取数组arr中的最大值。
 
    int iexp;    /// 排序指数，iexp=1：按个位排序；iexp=10：按十位排序；......
 
    /// 从个位开始，对数组arr按指数位进行排序。
    for (iexp = 1; imax / iexp > 0; iexp = iexp * 10) {
        _radixsort(arr, len, iexp);
        int i;
        ///cout << iexp << " ";     ///输出指数
        for (i = 0; i < len; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
}
 
int main() {
    ///int arr[] = {144, 203, 738, 905, 347, 215, 836, 26, 527, 602, 946, 504, 219, 750, 848};
    ///int len = sizeof(arr) / sizeof(int);
    int len;
    cin >> len;
    int *data = new int[len];
    for (int i = 0; i < len; i++)
        cin >> data[i];
    for (int i = 0; i < len; i++)
        cout << data[i] << " ";
    cout<<endl;
 
    radixsort(data, len);  /// 基数排序。
 
    /// 显示排序结果。
    cout<<"显示最后排完序的结果："<<endl;
    for (int i = 0; i < len; i++)
        cout << data[i] << " ";
    cout << endl;
 
    return 0;
}
 
/**
输入：
15
144 203 738 905 347 215 836 26 527 602 946 504 219 750 848
输出：
144 203 738 905 347 215 836 26 527 602 946 504 219 750 848
750 602 203 144 504 905 215 836 26 946 347 527 738 848 219
602 203 504 905 215 219 26 527 836 738 144 946 347 848 750
26 144 203 215 219 347 504 527 602 738 750 836 848 905 946
显示最后排完序的结果：
26 144 203 215 219 347 504 527 602 738 750 836 848 905 946
*/

我是花花，祝自己也祝您变强了~