提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

经典算法:基数排序的小例子

经典算法 例子 基数排序
2023-06-13 09:14:47 时间

1.概述

基数排序(Radixsort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(TabulationMachine)上的贡献。

原理：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。基数排序的时间复杂度是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
       publicstaticvoidRadixSort(int[]nums,intdigit)
       {
           for(intk=1;k<=digit;k++)
           {
               int[]tmpArray=newint[nums.Length];
               int[]tmpCountingSortArray=newint[10];
               inti;

               for(i=0;i<nums.Length;i++)
               {
                   inttmpSplitDigit=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--)
               {
                   inttmpSplitDigit=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);

相关文章