排序---基数排序实现和性能分析

悠悠 2023-07-06 04:51 60阅读 0赞

## 基数排序 ##

#### 算法思想 ####

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。

#### 图解 ####

将数组 \{53, 3, 542, 748, 14, 214\} 使用基数排序, 进行升序排序

1.  事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9
2.  第1轮排序 ，按照个位排序，将 各个数，按照个位大小 放入到 对应的各个数组中  
    ![在这里插入图片描述][20200216122026449.png]
3.  然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出放入原数组中，第一轮排序后得到\{542 53 3 14 214 748 \}；第2轮排序，按照十位排序  
    ![在这里插入图片描述][20200216122055397.png]
4.  第二轮排序后得到\{ 3 14 214 542 748 53\}；第3轮排序，按照百位排序  
    ![在这里插入图片描述][20200216122224236.png]
5.  第三轮排序后得到\{3 14 53 214 542 748\}

#### 实现 ####

public class RadixSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(100);
            }
            System.out.println(Arrays.toString(arr));
            radixSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void radixSort(int[] arr) { 
            //1.先找出最大值的位数，设为length
            //2.循环length次，依次将元素按照个位、十位、百位...(没有该位次的用0填充)放入桶中
            //3.每次循环需要记录当前每个桶的有效元素个数，记录在数组bucketItemCount中
            //4.每次循环完后，把桶中的元素依次取出放入arr中，并将bucketItemCount元素置0
    
            int max = arr[0];
            int length = arr.length;
            int maxLength;  //arr中元素的最大位数
            int[][] buckets; //桶
            int[] bucketItemCount; //每个桶的有效元素个数
            int arrCounter = 0; //计数器，从桶中取元素放入原数组中时，记录原数组下标
    
            for(int i = 0; i < length; i++) { 
                if(arr[i] > max) { 
                    max = arr[i];
                }
            }
            maxLength = (max + "").length();
            buckets = new int[10][length];
            bucketItemCount = new int[10];
    
            for(int j = 0, n = 1; j < maxLength; j++, n *= 10) { 
                //遍历数组中的每个元素，分别按照个位、十位...放入桶中
                for(int k = 0; k < length; k++) { 
                    int digitOfElement = (arr[k] / n) % 10;
                    buckets[digitOfElement][bucketItemCount[digitOfElement]++] = arr[k];
                }
                //遍历每一个桶，把桶中的元素依次取出放入arr中
                arrCounter = 0;
                for(int m = 0; m < 10; m++) { 
                    //遍历第m个桶，bucketItemCount[m]是第m个桶中有效元素的个数
                    for(int p = 0; p < bucketItemCount[m]; p++) { 
                        arr[arrCounter++] = buckets[m][p];
                    }
                    bucketItemCount[m] = 0;
                }
            }
        }
    }

## 性能分析 ##

1.  **稳定的**
2.  平均情况、最好情况、最坏情况时间复杂度都是**O(d(r+n))**，n代表待排序数据个数，d表示关键码个数（如对数字排序，关键码就是0~9这10个数字，对字符串排序，关键码就是52个大小写字母，如果不区分大小写，则关键码是26个字母），r表示关键码的取值范围。  
    其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O®，共进行d趟分配和收集。
3.  **空间复杂度是O(n+r)**

[20200216122026449.png]: https://img-blog.csdnimg.cn/20200216122026449.png
[20200216122055397.png]: https://img-blog.csdnimg.cn/20200216122055397.png
[20200216122224236.png]: https://img-blog.csdnimg.cn/20200216122224236.png