八大排序算法之基数排序

素颜马尾好姑娘i 2022-05-20 08:06 272阅读 0赞

**一、简单介绍**

**1、基数排序也就是桶排序，属于分配式排序。**

**2、特点：按照分配、按序回收(分配到不同的位置上,然后回收...)，不断分配....不断按序回收，直到有序为止。**

**3、时间复杂度：O(nlog(r)m)        **

**       (1)r表示所采用的基数**

**       (2)m表示堆数**

**4、算法思路：**

**      (1) 将所有的数依次按照个位、十位、百位、千位、.....进行多次分配和按序回收。**

**      (2) 每次排序的结果都按照目前排序位的大小进行按序回收。**

**      (3) 将按序回收的结果给下次排序进行高一位的分配，然后继续进行高一位的按序回收。**

**      (4) 这样，一直到(最大值的位数+1)次后，排序就结束了，就可以输出结果了。**

** **

**二、算法实现**

**(1)工具：IDEA**

**     JDK：1.8.0\_152**

**(2)代码：**

package com.atlihao;
    
    //排序算法测试类
    public class RadixTest {
        public static void main(String[] args) {
            int[] arrays = {1, 22, 10, 199, 30, 1008, 20, 300};
            radixSort(arrays);
            exportResult(arrays);
        }
    
        //一次排序和回收
        public static void radixSort(int[] arrays) {
            int max = findMax(arrays, 0, arrays.length - 1);
            for (int i = 1; max / i > 0; i = i * 10) {
                int[][] buckets = new int[arrays.length][10];
                for (int j = 0; j < arrays.length; j++) {
                    int num = (arrays[j] / i) % 10;
                    buckets[j][num] = arrays[j];
                }
    
                int k = 0;
                //回收
                for (int j = 0; j < 10; j++) {
                    for (int m = 0; m < arrays.length; m++) {
                        if (buckets[m][j] != 0) {
                            arrays[k] = buckets[m][j];
                            k++;
                        }
                    }
                }
            }
        }
    
    
        /**
         * 递归,找出最大的值
         *
         * @param arrays
         * @param L      左边界,第一个数
         * @param R      有边界,最后一个数(数组的长度)
         * @return
         */
        public static int findMax(int[] arrays, int L, int R) {
    
            //如果该数组只有一个数,那么最大的就是该数组的第一个值
            if (L == R) {
                return arrays[L];
            } else {
                int a = arrays[L];
                int b = findMax(arrays, L + 1, R);   //找出整体最大的值
                if (a > b) {
                    return a;
                } else {
                    return b;
                }
            }
        }   
      //输出数组方法
        public static void exportResult(int[] arrays) {
            for (int i = 0; i < arrays.length; i++) {
                if (i == 0) {
                    System.out.print("基数排序得到的数组:{" + arrays[i] + ",");
                } else if (i == (arrays.length - 1)) {
                    System.out.print(arrays[i] + "}");
                } else {
                    System.out.print(arrays[i] + ",");
                }
            }
        }
    }

**三、注意点**

`   (1) 排序的次数等于该数组中的最大值的位数+1。`

**      (2)  基数排序不适合对含有0或者负数的数组进行排序。**