算法学习（七）——基数排序

朱雀 2022-07-12 07:19 149阅读 0赞

# 算法学习（七）——基数排序 #

[基数排序][Link 1]（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的[元素分配][Link 2]至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其[时间复杂度][Link 3]为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。（摘自百度百科）

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。（摘自百度百科）  
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。（摘自百度百科）

问题：给定数组，进行排序

方法：基数排序

实现：

package com.xueyou;
    
    public class RadixSort {
        /**
         * 打印数组
         *
         * @param a
         */
        static void printArray(int[] a) {
            for (int num : a) {
                System.out.print(num + "\t");
            }
            System.out.println("");
        }
    
        static void radixSort(int[] a, int d) {
            int i = 1;
            int n = 1;
            //负责临时保存数组中属于每一位的值
            int[][] temp = new int[10][a.length];
            //负责记录每一位的个数
            int[] count = new int[10];
            while (i <= d) {
                for (int j = 0; j < a.length; j++) {
                    int lsd = (a[j] / n) % 10;
                    temp[lsd][count[lsd]] = a[j];
                    count[lsd]++;
                }
                for (int j = 0, k = 0; j < 10; j++) {
                    if (count[j] > 0) {
                        for (int m = 0; m < count[j]; m++) {
                            a[k] = temp[j][m];
                            k++;
                        }
                    }
                }
                for (int j = 0; j < count.length; j++) {
                    count[j] = 0;
                }
                printArray(a);
                i++;
                n *= 10;
            }
        }
    
        public static void main(String[] args) {
            int[] a = {23, 3, 41, 53, 26, 75, 34, 83, 13, 75, 34, 0, 123};
            printArray(a);
            System.out.println("==================排序中=====================");
            radixSort(a, 3);
            System.out.println("==================排序中=====================");
            printArray(a);
        }
    }

运行结果：

![Center][]

[Link 1]: http://baike.baidu.com/view/1170573.htm
[Link 2]: http://baike.baidu.com/view/2914896.htm
[Link 3]: http://baike.baidu.com/view/104946.htm
[Center]: /images/20220711/0aa7e6c969dc48edad109df043bbeda9.png