当前位置：首页 > news >正文

基数排序（学习）

news 来源：原创 2024/5/12 19:20:08

一、基数排序描述

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

二、基数排序描述

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

三、实现步骤

（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 List<List<int>>();
        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;
    }

五、应用场景