基数排序java

超、凢脫俗 2022-06-06 07:59 180阅读 0赞

参考：  
[http://blog.csdn.net/lemon\_tree12138/article/details/51695211][http_blog.csdn.net_lemon_tree12138_article_details_51695211]  
[http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html][http_www.cnblogs.com_Braveliu_archive_2013_01_21_2870201.html]

基数排序是一种分配–收集式的排序。通过下面的实例来看下整个过程：

初始的待排序数组如下所示：

73  22  93  43  55  14  28  65  39  81

创建一个二维的数组，第一维代表某一位的值，第二维填充该位值都相等的元素。

首先根据个位的值，往桶中分配  
![image][]

再收集：

81  22  73  93  43  14  55  65  28  39

根据十位，分配

![image][image 1]

再收集：

14  22  28  39  43  55  65  73  81  93

排序就结束了，如果有更高位，继续这个分配和收集的过程。

基数排序分为LSD（Least significant digital）或MSD（Most significant digital），  
LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。

时间效率 ：设待排序列为n个记录，d个关键码（我理解是位数），关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

java实现代码：

public class RadixSort {
        private static void radixSort(int[] array, int d) { // d 表示范围
            int n=1;       //代表对应的数：1,10，100
            int k=0;
            int length = array.length;
            int[][] bucket = new int[10][length]; //排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
            int[] order = new int[length];  //保存每个桶里有多少数字，二维数组纵坐标； 单纯是为了记录个数
            while (n < d) {
                for (int num : array) {
                    int digit = (num/n)%10;
                    bucket[digit][order[digit]] = num;
                    order[digit]++;
                }
                for (int i=0; i<length; i++) {  //将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一轮的排序结果
                    if (order[i]!=0) {  //如果桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                        for (int j=0; j<order[i]; j++) {
                            array[k] = bucket[i][j];
                            k++;
                        }
                    }
                    order[i] = 0; //将桶里计数器置0，用于下一次排序
                }
                n *= 10;
                k = 0;  // 将k置0，用于下一轮保存排序结果
            }
        }
    
        public static void main(String[] args)
        {
            int[] A=new int[]{
       73,22, 93, 43, 55, 14, 28, 65, 39, 81};
            radixSort(A, 100);
            for(int num:A)
            {
                System.out.println(num);
            }
        }
    }

[http_blog.csdn.net_lemon_tree12138_article_details_51695211]: http://blog.csdn.net/lemon_tree12138/article/details/51695211
[http_www.cnblogs.com_Braveliu_archive_2013_01_21_2870201.html]: http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html
[image]: /images/20220606/bee4f28cd4cb4ee18cf7de2a9528f1ec.png
[image 1]: /images/20220606/63bac58c818c4072bd869bdf15ca9148.png