【排序算法】- 基数排序

桃扇骨 2023-02-19 08:27 11阅读 0赞

## 排序动图 ##

![aHR0cHM6Ly95dXUtYmxvZy5vc3MtY24tc2hlbnpoZW4uYWxpeXVuY3MuY29tL3JhZGl4U29ydC5naWY][]

## 排序思路 ##

将数组按基数进行排序，个位，十位，百位…

## 排序流程 ##

*  取数组中最大的数，并计算位数
 *  从最低位开始取每个位的数组成一个新的数组
 *  对新的数组重新按位排序，直到位数排完

## 代码实现 ##

public static void radixSort(int[] arr) { 
        // 找出最大的数
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i ++) { 
            if (arr[i] > max) { 
                max = arr[i];
            }
        }
        // 计算最大的数有几位
        int length = (max+"").length();
        // 存放每次排序后的数字
        int[] temp = arr;
        // temp 数组的下标
        int index = 0;
        // 排序 length 次 n 代表每次的需要取模的值
        for (int i = 0, n = 1; i < length; i++, n*=10) { 
            // 存放每个位置对应的数
            int[][] bucket = new int[10][arr.length];
            // 存放每个下标放了一个数字
            int[] counts = new int[10];
            // 排序
            for (int j = 0; j < arr.length; j++) { 
                // 取模放入对应的数组中
                int indexVal = temp[j] / n % 10;
                bucket[indexVal][counts[indexVal]] = temp[j];
                counts[indexVal] = ++counts[indexVal];
            }
            // 将每个下标的数字按顺序取出来
            for (int k = 0; k < 10; k++) { 
                for (int l = 0; l < counts[k]; l++) { 
                    temp[index] = bucket[k][l];
                    index++;
                }
            }
            // index 归 0
            index = 0;
        }
        // 将临时数组赋予真实数组
        for (int i = 0; i < arr.length; i++) { 
            arr[i] = temp[i];
        }
    }

## 代码优化 - 使用队列记录数组 ##

*  自定义队列 `MyQueue.java`

public class MyQueue { 
    
        /** * 使用数组作为队列的底层 */
        private int[] arr;
    
        /** * 构造方法 */
        public MyQueue() { 
            arr = new int[0];
        }
    
        /** * 入队 * * @param e 入队的元素 */
        public void add(int e) { 
            // 创建一个新的数组
            int[] newArray = new int[arr.length + 1];
            // 将数据复制到新数组
            for (int i = 0; i < arr.length; i++) { 
                newArray[i] = arr[i];
            }
            // 入队
            newArray[arr.length] = e;
            // 将新数组赋值给原来的数组
            arr = newArray;
        }
    
        /** * 出队 * * @return 出队的元素 */
        public int poll() { 
            // 队列是否为空
            if (isEmpty()) { 
                throw new RuntimeException("Queue is Empty");
            }
            // 记录出队的元素
            int e = arr[0];
            // 创建一个新的数组
            int[] newArray = new int[arr.length-1];
            // 将数据复制到新数组
            for (int i = 0; i < newArray.length; i++) { 
                newArray[i] = arr[i+1];
            }
            // 将新数组赋值给原来的数组
            arr = newArray;
            // 返回出队的元素
            return e;
        }
    
        /** * 队列是否为空 * * @return true/false */
        public boolean isEmpty() { 
            return arr.length == 0;
        }
    }

*  使用队列优化技术排序 `RadixQueueSort.java`

public class RadixQueueSort { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 54, 4, 36, 125, 435, 52, 23, 678, 34, 12, 879};
            radixQueueSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        /** * 使用队列实现基数排序 * * @param arr 数组 */
        public static void radixQueueSort(int[] arr) { 
            // 定义最大值，找出最大的数
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < arr.length; i++) { 
                if (max < arr[i]) { 
                    max = arr[i];
                }
            }
            // 计算最大值的位数
            int length = (max + "").length();
            // 定义一个记录数字的队列数组 0 1 2 3 4 ...
            MyQueue[] myQueue = new MyQueue[10];
            // 为每个队列初始化
            for (int i = 0; i < myQueue.length; i++) { 
                myQueue[i] = new MyQueue();
            }
            // 定义一个记录排序好的数组
            int[] temp = arr;
            // 记录临时数组的下标
            int index = 0;
            // 循环基数排序
            for (int i = 0, n = 1; i < length; i++, n *= 10) { 
                // 遍历所有数据
                for (int j = 0; j < temp.length; j++) { 
                    // 计算余数
                    int indexVal = temp[j] / n % 10;
                    // 加入对应余数的队列
                    myQueue[indexVal].add(temp[j]);
                }
                // 取出队列中的数据
                for (int k = 0; k < myQueue.length; k++) { 
                    while (!myQueue[k].isEmpty()) { 
                        temp[index] = myQueue[k].poll();
                        index++;
                    }
                }
                // 将 index 初始为 0
                index = 0;
            }
            // 将临时数组赋值给原来的数组
            for (int i = 0; i < arr.length; i++) { 
                arr[i] = temp[i];
            }
        }
    }

[aHR0cHM6Ly95dXUtYmxvZy5vc3MtY24tc2hlbnpoZW4uYWxpeXVuY3MuY29tL3JhZGl4U29ydC5naWY]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly95dXUtYmxvZy5vc3MtY24tc2hlbnpoZW4uYWxpeXVuY3MuY29tL3JhZGl4U29ydC5naWY