基数排序（学习）

一、基数排序描述

1. 基数排序(radix sort)属于分配式排序,又被称为桶子法,它是通过键值的各个位的值,将要排序的元素分配至某些桶中,达到排序的作用
2. 基数排序法属于稳定的排序,基数排序法的是效率高的稳定性排序法
3. 基数排序是桶排序的扩展

二、基数排序描述

        将所有待比较数值统一为同样的数位长度,数为较短的数前面补零,然后,从最低位开始,依次进行一次排序.这样从最低位排序一直到最高为排序完成后,数列就变成了一个有序序列

三、实现步骤

（1）确定数组中的最大元素有几位（MAX）（确定执行的轮数）

（2）创建0~9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成

（3）依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直

         至MAX轮结束输出数组。

（4）具体实现步骤如下图

 四、代码实现

public int[] RadixSort(int[] array)
    {
        int max = array[0];
        foreach (var item in array)
        {
            max = item > max ? item : max;
        }
 
        int maxDigit = 0;       //得到最外层桶子的数量（便利几次）
        while (max != 0)
        {
            max /= 10;
            maxDigit++;
        }
 
        //创建新桶
        var bucket = new Listint>>();
        for (int i = 0; i < 10; i++)
        {
            bucket.Add(new List<int>());
        }
 
 
        //此处的代码对应（三、实现步骤，图文结合易于理解）
        for (int i = 0; i < maxDigit; i++)
        {
            //从个位到最高位，依次填充到对应的桶子中去
            int div = (int)Math.Pow(10, (i + 1));   
            foreach (var item in array)
            {
                int radix = (item % div) / (div / 10);
                bucket[radix].Add(item);
            }
 
            //将桶中的数据反向填充到数组中
            int index = 0;
            foreach (var item in bucket)
            {
                foreach (var it in item)
                {
                    array[index++] = it;
                }
                item.Clear();
            }
        }
        return array;
    }

 五、应用场景

• 在某个数字可能很大的时候，基数排序没有任何性能上的优势，还会浪费非常多的内存。

• 适用于代比较数组中元素，长度大概相同的情况，如：手机号排序、字符串排序和身份证排序等。

参考文档：基数排序（详细图解）

C# 算法之基数排序排序(非比较排序之三) - 灰信网（软件开发博客聚合）

数据结构与算法(17):基数排序及其应用实例