首页 / 算法 / 经典算法:基数排序的小例子
经典算法:基数排序的小例子
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了经典算法:基数排序的小例子，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1773字，纯文字阅读大概需要3分钟。
内容图文
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);
原文：http://www.jb51.net/article/34514.htm
内容总结
以上是互联网集市为您收集整理的经典算法:基数排序的小例子全部内容，希望文章能够帮你解决经典算法:基数排序的小例子所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。