欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

经典算法:基数排序的小例子

程序员文章站 2024-03-03 15:34:58
1.概述 基数排序(radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日...

1.概述

基数排序(radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(tabulation machine)上的贡献。

原理:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的时间复杂度是 o(k·n),其中n是排序元素个数,k是数字位数。

理解:类似【经典算法】第八回:桶排序,这里总是需要10个桶,多次使用,首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,然后再以十位数进行桶排序,依此类推。

如有 待排序数组[62,14,59,88,16]简单点五个数字,分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

|  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 |

|  0  |  1  |  2  |  3  |  4 |  5  |  6  |  7  |  8  |  9  |桶编号

将桶里的数字顺序取出来,输出结果:[62,14,16,88,59]

再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

|  0  | 14,16 |  0  |  0  |  0  | 59 | 62  | 0  | 88  |  0  |

|  0  |  1      |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶编号

因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可

最后输出结果:[14,16,59,62,88]

2.示例

复制代码 代码如下:

//基数排序 c# code
        public static void radixsort(int[] nums, int digit)
        {
            for (int k = 1; k <= digit; k++)
            {
                int[] tmparray = new int[nums.length];
                int[] tmpcountingsortarray = new int[10];
                int i;

                for (i = 0; i < nums.length; i++)
                {
                    int tmpsplitdigit = nums[i] / (int)math.pow(10, k - 1) - (nums[i] / (int)math.pow(10, k)) * 10;
                    tmpcountingsortarray[tmpsplitdigit]++;
                }
                for (i = 1; i < tmpcountingsortarray.length; i++)
                {
                    tmpcountingsortarray[i] += tmpcountingsortarray[i - 1];
                }
                for (i = nums.length - 1; i >= 0; i--)
                {
                    int tmpsplitdigit = nums[i] / (int)math.pow(10, k - 1) - (nums[i] / (int)math.pow(10, k)) * 10;
                    tmparray[tmpcountingsortarray[tmpsplitdigit] - 1] = nums[i];
                    tmpcountingsortarray[tmpsplitdigit]--;
                }
                for (i = 0; i < nums.length; i++)
                {
                    nums[i] = tmparray[i];
                }
            }
        }
            //int[] list = new[] { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };
            //sorter.radixsort(list, 2);