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);
基数排序
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
更新日志
- 纯音入心系列纯音乐《中央民族乐团-古筝传奇》1CD[MP3][253.1MB]
- 江玲.1989-这样你才爱我,是吗?【新作有声】【WAV+CUE】
- 郭美美.2010-我是郭美美【华纳】【WAV+CUE】
- 黄心懋1991-轻忧郁【滚石】【WAV+CUE】
- 群星.2000-大地金曲世纪回顾2CD【大地】【WAV+CUE】
- 王菲.1996-浮躁(2024环球MQA-UHQCD限量版)【环球】【WAV+CUE】
- 群星.2022-传家电视剧原声带【东阳欢娱】【FLAC分轨】
- 《摇滚教父 伍佰黄金精选 2CD》 [WAV+CUE][1GB]
- 《凤凰传奇 我从草原来》[WAV/分轨][400MB]
- 《叶倩文 真心真意过一生》[WAV+CUE][400MB]
- 潘越云.1985-世间女子(滚石25周年经典复刻版)【滚石】【WAV+CUE】
- 陈柏宇.2009-CANT.BE.HALF【SONY】【WAV+CUE】
- 李明依.1989-小女生【滚石】【WAV+CUE】
- 《李荣浩 新时代创作新人王》[WAV分轨][310MB]
- 《黑鸭子与马头琴 史上最动听草原音乐》[WAV+CUE][320MB]