一, 动图演
二, 思路分析
基数排序第 i 趟将待排数组里的每个数的 i 位数放到 tempj(j=1-10) 队列中, 然后再从这十个队列中取出数据, 重新放到原数组里, 直到 i 大于待排数的最大位数.
1. 数组里的数最大位数是 n 位, 就需要排 n 趟, 例如数组里最大的数是 3 位数, 则需要排 3 趟.
2. 若数组里共有 m 个数, 则需要十个长度为 m 的数组 tempj(j=0-9) 用来暂存 i 位上数为 j 的数, 例如, 第 1 趟, 各位数为 0 的会被分配到 temp0 数组里, 各位数为 1 的会被分配到 temp1 数组里......
3. 分配结束后, 再依次从 tempj 数组中取出数据, 遵循先进先进原则, 例如对数组 {1,11,2,44,4}, 进行第 1 趟分配后, temp1={1,11},temp2={2},temp4={44,4}, 依次取出元素后 {1,11,2,44,4}, 第一趟结束
4. 循环到 n 趟后结束, 排序完成
根据思路分析, 每一趟的执行流程如下图所示:
通过基数排序对数组 {53, 3, 542, 748, 14, 214, 154, 63, 616}:
三, 负杂度分析
1. 时间复杂度:
每一次关键字的桶分配都需要 O(n) 的时间复杂度, 而且分配之后得到新的关键字序列又需要 O(n) 的时间复杂度.
假如待排数据可以分为 d 个关键字, 则基数排序的时间复杂度将是 O(d*2n) , 当然 d 要远远小于 n, 因此基本上还是线性级别的.
系数 2 可以省略, 且无论数组是否有序, 都需要从个位排到最大位数, 所以时间复杂度始终为 O(d*n) . 其中, n 是数组长度, d 是最大位数.
2. 空间复杂度:
基数排序的空间复杂度为 O(n+k), 其中 k 为桶的数量, 需要分配 n 个数.
四, Java 代码如下
- import java.util.Arrays;
- public class Main {
- public static void main(String[] args) {
- int[] arr = new int[]{10,6,3,8,33,27,66,9,7,88};
- radixSort(arr);
- }
- private static void radixSort(int[] arr) {
- // 求出待排数的最大数
- int maxLength=0;
- for (int i = 0; i < arr.length; i++) {
- if(maxLength<arr[i])
- maxLength = arr[i];
- }
- // 根据最大数求最大长度
- maxLength = (maxLength+"").length();
- // 用于暂存数据的数组
- int[][] temp = new int[10][arr.length];
- // 用于记录 temp 数组中每个桶内存的数据的数量
- int[] counts = new int[10];
- // 用于记录每个数的 i 位数
- int num = 0;
- // 用于取的元素需要放的位置
- int index = 0;
- // 根据最大长度决定排序的次数
- for (int i = 0,n=1; i < maxLength; i++,n*=10) {
- for (int j = 0; j < arr.length; j++) {
- num = arr[j]/n%10;
- temp[num][counts[num]] = arr[j];
- counts[num]++;
- }
- // 从 temp 中取元素重新放到 arr 数组中
- for (int j = 0; j < counts.length; j++) {
- for (int j2 = 0; j2 < counts[j]; j2++) {
- arr[index] = temp[j][j2];
- index++;
- }
- counts[j]=0;
- }
- index=0;
- }
- System.out.println(Arrays.toString(arr));
- }
- }
来源: https://www.cnblogs.com/l199616j/p/10738568.html