• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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);


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
ASP.NET中ListView(列表视图)的使用前台绑定附源码发布时间:2022-02-05
下一篇:
.net邮箱发布邮箱信息的实例发布时间:2022-02-05
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap