PCB挺有意思的基数排序----C#代码实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

今天在头条看一个很有意思的排序算法【基数排序】，以前所学习的排序算法都是基于数值对比的方式排序的,而这个算法挺有意思的非常独特。但从网上看到的例子通常是对个位,十位处理，并转为对应的桶索引的方式实现，这里将此算法用C#实现，并以位运算的新方式实现。

一.代码实现

        static void Main(string[] args)
        {
            //待排序数组
            List<int> arrlist = new List<int>() { 72, 11, 82, 32, 44, 13, 17, 95, 54, 28, 79, 56 };
            int Number = 3;               //基数   网上教材都是基于个位，十位，百位进行运算，这里通过位数计算
            int NumCount = 1 << Number;   //桶数   位数是3那么桶数是8，  位数是4那么桶数是16
            List<List<int>> intList = new List<List<int>>(); //建立好桶 
            for (int i = 0; i < NumCount; i++)
            {
                intList.Add(new List<int>());
            }
            int LayerCount = 3; //位数划分组数(计算方法：数组最大值为95,对应二进制为:1011111,基数为3的话，可以分为1,011,111; 组数为3)
            //算法实现-----算法复杂度(nxm)
            for (int k = 1; k <= LayerCount; k++) //最大整数最高位数划分组数
            {
                intList.ForEach(tt => tt.Clear());
                foreach (var item in arrlist)
                {
                    int index = item & ((1 << k * Number) - 1); //左移加与位运算 求桶索引   
                    index = index >> (k - 1) * Number;//右移加与运算  求桶索引   
                    intList[index].Add(item);
                }
                arrlist.Clear();
                for (int i = 0; i < NumCount; i++)
                {
                    for (int j = 0; j <intList[i].Count; j++)
                    {
                        arrlist.Add(intList[i][j]);
                    }
                }
            }
            //输出
            arrlist.ForEach(tt=>Console.WriteLine(tt));
            Console.ReadKey();
        }