c++ 基数排序

基数排序

题目和我的前几个排序一样

AC代码

#include <bits/stdc++.h>
using namespace std;
int ArrLength(int Arr[]) //测出int数组的长度 
{
    int i = 0; 
    while (Arr[i])
        i ++;
    return i;
}
    /**
     * 递归，找出数组最大的值
     *
     * @param arrays 数组
     * @param L      左边界，第一个数
     * @param R      右边界，数组的长度
     * @return
     */
int findMax(int arrays[],int L,int R)
{
    //如果该数组只有一个数，那么最大的就是该数组第一个值了
    if (L == R)
    return arrays[L];
    else
    {
        int a = arrays[L];
        int b = findMax(arrays, L + 1, R);//找出整体的最大值
        if (a > b)
            return a;
        else
        {
            return b;
        }
    }
}
void radixSort(int arrays[])
{
    int max = findMax(arrays, 0,ArrLength(arrays) - 1);
    //需要遍历的次数由数组最大值的位数来决定
    for (int i = 1; max / i > 0; i = i * 10)
    {
        int buckets[ArrLength(arrays)][10];
        //获取每一位数字(个、十、百、千位...分配到桶子里)
        memset(buckets,0,sizeof(buckets));//【重点】一定要memset 一定要memset 否则会内存泄漏(Segmentation fault) 
        for (int j = 0; j < ArrLength(arrays); j++)
        {
            int num = (arrays[j] / i) % 10;
            //将其放入桶子里
            buckets[j][num] = arrays[j];
        }
        //回收桶子里的元素
        int k = 0;
        //有10个桶子
        for (int j = 0; j < 10; j++)
        {
             //对每个桶子里的元素进行回收
            for (int l = 0; l < ArrLength(arrays); l++)
            {
                //如果桶子里面有元素就回收(数据初始化会为0)
                if (buckets[l][j] != 0)
                {
                    arrays[k++] = buckets[l][j];
                }
            }
        }
    }
}
int main()
{
    int arrays[100] = {73,22,93,43,55,14,28,65,39,81};
    radixSort(arrays);
    for (int i = 0;i <= ArrLength(arrays) - 1 ;i ++)
        cout << arrays[i] << " ";
    return 0;
}

思路

假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步：
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步：
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

总结

基数排序没有关键字的比较，通过"分配"和"收集"过程来实现排序
排序过程中，要注意"分配"和"收集"的顺序（重点）

概念

基数排序是一种借助于多关键字排序的思想对单关键字排序的方法，是通过"分配"和"收集"的过程来实现排序.

参考链接:
[https://v.youku.com/v_show/id_XMTYxNjYzNjYwNA==.html?spm=a2h0k.11417342.soresults.dtitle]

c++ 基数排序

原文：https://www.cnblogs.com/LJA001162/p/11217276.html