C#算法设计排序篇之09-基数排序(附带动画演示程序)
2024-09-07 06:49:24
基数排序(Radix Sort)
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/691 访问。
基数排序属于“分配式排序”(Distribution Sort),它是透过键值的部份信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为 ,其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
示例:
public class Program {
public static void Main(string[] args) {
int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
RadixSort(array, 10);
ShowSord(array);
Console.ReadKey();
}
private static void ShowSord(int[] array) {
foreach (var num in array) {
Console.Write($"{num} ");
}
Console.WriteLine();
}
public static void RadixSort(int[] array, int bucketNum) {
int maxLength = MaxLength(array);
//创建bucket时,在二维中增加一组标识位,其中bucket[x, 0]表示这一维所包含的数字的个数
//通过这样的技巧可以少写很多代码
int[,] bucket = new int[bucketNum, array.Length + 1];
for (int i = 0; i < maxLength; i++) {
foreach (var num in array) {
int bit = (int)(num / Math.Pow(10, i) % 10);
bucket[bit, ++bucket[bit, 0]] = num;
}
for (int count = 0, j = 0; j < bucketNum; j++) {
for (int k = 1; k <= bucket[j, 0]; k++) {
array[count++] = bucket[j, k];
}
}
//最后要重置这个标识
for (int j = 0; j < bucketNum; j++) {
bucket[j, 0] = 0;
}
}
}
private static int MaxLength(int[] array) {
if (array.Length == 0) return 0;
int max = array[0];
for (int i = 1; i < array.Length; i++) {
if (array[i] > max) max = array[i];
}
int count = 0;
while (max != 0) {
max /= 10;
count++;
}
return count;
//return (int)Math.Log10(max) + 1;
}
}
以上是基数排序算法的一种实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/691 访问。
8 11 21 28 32 43 48 56 69 72 80 94
分析:
基数排序算法的时间复杂度为: ,其中r为所采取的基数,m为堆数。
AlgorithmMan:
AlgorithmMan by Iori,AlgorithmMan是使用C#开发的一套用于算法演示的工具。
最新文章
- php后台开发(二)Laravel框架
- iptables 开启3306端口
- C#常用日期格式处理转换[C#日期格式转换大全
- VS模板文件修改,自动生成注释
- Difference between 2>;&;-, 2>;/dev/null, |&;, &;>;/dev/null and >;/dev/null 2>;&;1
- BZOJ_1031_[JSOI2007]_字符串加密_(后缀数组)
- jQuery技术内幕电子版5
- Linux文件的查找
- python的try方法中的else和finally的区别
- 团队作业八——第二次团队冲刺(Beta版本)第3天
- python画手绘图
- python 练习3
- 老生常谈:Windows的7类安全漏洞
- 基于 Python 和 Pandas 的数据分析(5) --- Concatenating and Appending
- mac/linux 修改vim显示信息
- 005_ss-link.info的ping探测工具
- QrenCode : 命令行下生成二维码图片
- 2-nginx 安装
- 大数据入门:Maven项目的创建及相关配置
- 2017-2018-1 20155317 IPC