鸟语天空

基数排序

作者：追风剑情 发布于：2019-6-22 17:12 分类：Algorithms

示例

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
using System.Data.SQLite;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 79, 48, 65, 10, 55};
            int r = 10;
            int d = 2;
            int[] arr1 = RadixSortHelper.Sort(arr, r, d);

            Console.Write("原数组：");
            for (int i = 0; i < arr.Length; i++)
                Console.Write(arr[i] + " ");

            Console.WriteLine();

            Console.Write("排序后：");
            for (int i = 0; i < arr1.Length; i++)
                Console.Write(arr1[i] + " ");

            Console.ReadKey();
        }
    }

    public class RadixSortHelper
    {
        /// <summary>
        /// 基数排序
        /// 原理：
        /// 如果关键字为整数，先按关键字的个位排序，再按关键字的十位排序，......
        /// 基数排序是稳定的，时间复杂度为O(d(n+r))
        /// </summary>
        /// <param name="arr">待排序数组</param>
        /// <param name="r">基数,如：十进制就为10</param>
        /// <param name="d">关键字位数</param>
        public static int[] Sort(int[] arr, int r, int d)
        {
            //需要用到一个辅助队列
            Node[] nodes = new Node[r];
            for (int i = 0; i < r; i++)
                nodes[i] = new Node();

            for (int i = 0; i < d; i++)
            {
                for (int j = 0; j < arr.Length; j++)
                {
                    int a = arr[j];
                    int k = Conversion(a, i);
                    //将数据分配到队列中
                    nodes[k].list.Add(a);
                }
                //从队列中重新收集数据
                arr = Allocation(nodes);
            }
            return arr;
        }

        private static int[] Allocation(Node[] nodes)
        {
            List<int> list = new List<int>();
            for(int i=0; i<nodes.Length; i++)
            {
                Node node = nodes[i];
                if (node.list.Count > 0)
                {
                    list.AddRange(node.list.ToArray());
                    node.list.Clear();
                }
            }
            return list.ToArray();
        }

        private static int Conversion(int x, int i)
        {
            switch(i)
            {
                case 0: //提取x的个位数
                    x = x % 10;
                    break;
                case 1: //提取x的十位数
                    x = x / 10;
                    break;
                default:
                    x = x / (int)Math.Pow(10, i);
                    break;
            }
            return x;
        }

        private class Node
        {
            public List<int> list = new List<int>();
        }
    }
}

运行测试

标签: Algorithms