c#基数排序Radix sort的实现方法

经典排序算法 - 基数排序Radix sort

原理类似桶排序,这里总是需要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]

代码仅供参考

代码如下:

/// <summary>
        /// 基数排序
        /// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可
/// </summary>
        /// <param name="unsorted">待排数组</param>
        /// <param name="array_x">桶数组第一维长度</param>
        /// <param name="array_y">桶数组第二维长度</param>
        static void radix_sort(int[] unsorted, int array_x = 10, int array_y = 100)
        {
            for (int i = 0; i < array_x/* 最大数字不超过999999999...(array_x个9) */; i++)
            {
                int[,] bucket = new int[array_x, array_y];
                foreach (var item in unsorted)
                {
                    int temp = (item / (int)Math.Pow(10, i)) % 10;
                    for (int l = 0; l < array_y; l++)
                    {
                        if (bucket[temp, l] == 0)
                        {
                            bucket[temp, l] = item;
                            break;
                        }
                    }
                }
                for (int o = 0, x = 0; x < array_x; x++)
                {
                    for (int y = 0; y < array_y; y++)
                    {
                        if (bucket[x, y] == 0) continue;
                        unsorted[o++] = bucket[x, y];
                    }
                }
            }
        }

static void Main(string[] args)
        {
            int[] x = { 999999999, 65, 24, 47, 13, 50, 92, 88, 66, 33, 22445, 10001, 624159, 624158, 624155501 };
            radix_sort(x);
            foreach (var item in x)
            {
                if (item > 0)
                    Console.WriteLine(item + ",");
            }
            Console.ReadLine();
        }

赞 (0)

相关推荐

  • C#基础之数组排序、对象大小比较实现代码

    从个小例子开始: 复制代码 代码如下: int[] intArray = new int[]{2,3,6,1,4,5}; Array.Sort(intArray); Array.ForEach<int>(intArray,(i)=>Console.WriteLine(i)); 这个例子定义了一个int数组,然后使用Array.Sort(arr)静态方法对此数组进行排序,最后输出排序后的数组.以上例子将毫无意外的依次输出1,2,3,4,5,6. 为什么Array的Sort方法可以正确的对i

  • c#对list排序示例

    复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ListSort { class Program { static void Main(string[] args) { List listCustomer = new List(); listCustomer.Add(new Customer { name = "客户1",

  • C#归并排序的实现方法(递归,非递归,自然归并)

    C#归并排序的实现方法(递归,非递归,自然归并)

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{    class Program    {        static void Main(string[] args)        {            while (true)            {                Console.W

  • c#集合快速排序类实现代码分享

    说明: 1.集合类型参数化: 2.可根据集合中的对象的各个属性进行排序,传入属性名称即可: 注:属性必须实现了IComparable接口,C#中int.datetime.string等基本类型都已经实现了IComparable接口. 复制代码 代码如下: /// <summary>    /// 对集合进行排序,如    /// List<User> users=new List<User>(){.......}    /// ListSorter.SortList&l

  • C#实现Datatable排序的方法

    本文实例展示了C#实现Datatable排序的方法,分享给大家供大家参考之用.具体方法如下: 一般来说,在C#中要对Datatable排序,可使用DefaultView的Sort方法.需要先获取Datatable的DefaultView,然后设置得到的Dataview的sort属性,最后用视图的ToTable方法将排好序的dataview导出为Datatable. 代码如下: DataTable dt = new DataTable(); dt.Columns.Add("ID", ty

  • C#对DataTable里数据排序的方法

    直接给个实例代码吧 复制代码 代码如下: protected void Page_Load(object sender, EventArgs e)    {        DataTable dt = new DataTable();        dt.Columns.Add("Name");        dt.Columns.Add("Age");//因为是字符串,所以排序不对        dt.Rows.Add("小明", "

  • C#通过IComparable实现ListT.sort()排序

    本文实例讲述了C#通过IComparable实现ListT.sort()排序的方法,分享给大家供大家参考之用.具体方法如下: 通常来说,List<T>.sort()可以实现对T的排序,比如List<int>.sort()执行后集合会按照int从小到大排序.如果T是一个自定义的Object,可是我们想按照自己的方式来排序,那该怎么办呢,其实可以用过IComparable接口重写CompareTo方法来实现.流程如下: 一.第一步我们申明一个类Person但是要继承IComparabl

  • C#中DataTable排序、检索、合并等操作实例

    一.排序1.获取DataTable的默认视图2.对视图设置排序表达式3.用排序后的视图导出的新DataTable替换就DataTable(Asc升序可省略,多列排序用","隔开)1).重生法 复制代码 代码如下: dstaset.Tables.Add(dt)dataset.Tables(0).DefaultView.Sort = "id desc" 2).直接法 复制代码 代码如下: dv = New DataView(dt)dv.Sort = "id d

  • 深入IComparable与IComparer的排序实例详解

    如下所示: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Text;using System.Collections;namespace hgoApp{    class Comparer    {        static void Main()        {            Employee[] Employees = new Employee[5]; Employees[0] = ne

  • C# 键值对数据排序代码

    复制代码 代码如下: public static void SortDicWithLinq(){            Dictionary<DateTime, String> dd = new Dictionary<DateTime, String>();            DateTime dt = DateTime.Now;            dd.Add(dt, "bbb");            dd.Add(dt.AddDays(-1),&

  • c# 实现IComparable、IComparer接口、Comparer类的详解

    在默认情况下,对象的Equals(object o)方法(基类Object提供),是比较两个对象变量是否引用同一对象.我们要必须我自己的对象,必须自己定义对象比较方式.IComparable和ICompare 接口是.net framework 中比较对象的标准方式,这两个接口之间的区别如下:1. IComparable 在要比较的对象的类中实现,可以比较该对象和另一个对象.2.IComparer 在一个单独的类中实现,可以比较任意两个对象.一般情况下,我们使用 IComparable 给出类的

随机推荐