数据结构与算法——基数排序（改进的桶排序）

创作时间:

作者:

@小白创作中心

数据结构与算法——基数排序（改进的桶排序）

引用

CSDN

https://blog.csdn.net/weixin_43713707/article/details/137356145

基数排序是一种基于“分配式排序”思想的算法，通过将待排序元素分配到不同的桶中，然后依次取出实现排序。本文将详细介绍基数排序的基本原理、实现步骤，并通过代码示例帮助读者深入理解这一算法。

基数排序的基本思想

基数排序（radix sort）是“分配式排序”，又称“桶子法”（bucket sort）。它按照待排序元素的各个位的值，将待排元素分配到某个桶中，桶即为数组。接着通过一系列循环操作实现排序目的。由于基数排序不会改变相同值的元素的相对位置（前后顺序），所以其是稳定排序。

针对正整数，基数排序的一个简单思路是将整数按照位数切割成不同的数字，然后按每位进行比较和放入桶中。在桶排序之前，需要将待排序的元素置为统一的长度，位数较少的数字在前面补零。接着，从最低位开始，依次进行排序，将与对应位的值对应的数字放入对应的桶中，直到将最高位也按照规定放入桶中，从而得到的最终序列就是有序序列。

基数排序的实现步骤

下面通过一个具体的例子来说明基数排序的实现过程。假设要对数组 arr={53,3,542,748,14,214} 进行升序排序。

由于上述元素中最大数748为三位数，因此总共需要3轮排序，需要10个桶，桶下标分别为0，1，2，...9，恰好对应每位的数字0~9。首先将数字放入个位数字对应相同的桶下标的桶中，再按顺序取出桶中的元素，放入原始序列。然后对第1轮处理后的数组，对其十位数进行相同操作，将数字放入十位数字对应相同的桶下标的桶中，再按顺序取出桶中的元素，放入原始序列。最后对第2轮处理后的数组，对其百位数进行相同操作，最终就可以得到顺序排列的数组。

代码实现

下面是基数排序的具体代码实现：

public static void main(String[] args) {
    int[] arr = {53, 3, 542, 748, 14, 214};
    radixSort(arr);
}

public static void radixSort(int[] arr) {
    //第1轮排序（针对每个元素的个位进行排序处理）
    //定义一个二维数组，表示10个桶，每个桶是一个一维数组
    //说明：二维数组包含10个一维数组
    //为了防止在桶里放数据时溢出，则定义每个桶的大小的数组长度(最大)
    int[][] bucket = new int[10][arr.length];
    //为了记录每个桶里所放元素个数，定义一个一维数组，记录各个桶的每次放入的数据个数
    //bucketElementCounts[0]记录的就是bucket[0]这个桶 每次放入数据的个数
    int[] bucketElementCounts = new int[10];//记录10个桶，每个桶的数据的个数
    //第1轮，针对每个元素的个位进行排序处理
    for (int j = 0; j < arr.length; j++) {
        //取出每个元素的个位
        int digitOfElement = arr[j] / 1 % 10;
        //放入到对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
        bucketElementCounts[digitOfElement]++;//一个桶放入一个元素后，要递增
    }
    //按照桶里的元素顺序，（即一维数组的下标）依次取出数据，放入原来的数组
    int index = 0;
    //遍历每个桶，并将桶中数据，放入原数组
    for (int k = 0; k < bucketElementCounts.length; k++) {
        //如果桶中有数据，才将其数据放入原数组，如果桶里没有数据，则不用放
        if (bucketElementCounts[k] != 0) {//k桶才有数据
            //循环该桶，即第k个桶（第k个一维数组）
            for (int l = 0; l < bucketElementCounts[k]; l++) {
                //取出元素，放入到arr[]数组
                arr[index] = bucket[k][l];
                index++;
            }
        }
        //做完后，要把桶置零，bucketElements[k] = 0 !!!!!!!!!!
        bucketElementCounts[k] = 0;
    }
    //结果
    System.out.println("第1轮，对个位的排序处理： arr = " + Arrays.toString(arr));
    //第2轮，针对每个元素的十位进行排序处理
    for (int j = 0; j < arr.length; j++) {
        //取出每个元素的十位
        int digitOfElement = arr[j] / 10 % 10;
        //放入到对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
        bucketElementCounts[digitOfElement]++;//一个桶放入一个元素后，要递增
    }
    //按照桶里的元素顺序，（即一维数组的下标）依次取出数据，放入原来的数组
    index = 0;
    //遍历每个桶，并将桶中数据，放入原数组
    for (int k = 0; k < bucketElementCounts.length; k++) {
        //如果桶中有数据，才将其数据放入原数组，如果桶里没有数据，则不用放
        if (bucketElementCounts[k] != 0) {//k桶才有数据
            //循环该桶，即第k个桶（第k个一维数组）
            for (int l = 0; l < bucketElementCounts[k]; l++) {
                //取出元素，放入到arr[]数组
                arr[index] = bucket[k][l];
                index++;
            }
        }
        //做完后，要把桶置零
        bucketElementCounts[k] = 0;
    }
    //结果
    System.out.println("第2轮，对个位的排序处理： arr = " + Arrays.toString(arr));
    //第3轮，针对每个元素的百位进行排序处理
    for (int j = 0; j < arr.length; j++) {
        //取出每个元素的百位
        int digitOfElement = arr[j] / 100 % 10;//后面可以找规律
        //放入到对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
        bucketElementCounts[digitOfElement]++;//一个桶放入一个元素后，要递增
    }
    //按照桶里的元素顺序，（即一维数组的下标）依次取出数据，放入原来的数组
    index = 0;
    //遍历每个桶，并将桶中数据，放入原数组
    for (int k = 0; k < bucketElementCounts.length; k++) {
        //如果桶中有数据，才将其数据放入原数组，如果桶里没有数据，则不用放
        if (bucketElementCounts[k] != 0) {//k桶才有数据
            //循环该桶，即第k个桶（第k个一维数组）
            for (int l = 0; l < bucketElementCounts[k]; l++) {
                //取出元素，放入到arr[]数组
                arr[index] = bucket[k][l];
                index++;
            }
        }
        //要把桶清零
        bucketElementCounts[k] = 0;
    }
    //结果
    System.out.println("第3轮，对个位的排序处理： arr = " + Arrays.toString(arr));
}

通过上述分析，可以发现需要桶排的次数与最大位数的个数一样，因此通过简化，循环处理即可，得到最终的基数排序的代码为：

public static void main(String[] args) {
    int[] arr = {53, 3, 542, 748, 14, 214};
    radixSort(arr);
}

public static void radixSort(int[] arr) {
    //针对每一轮的分析，得到综合的循环排序方法
    //为了防止在桶里放数据时溢出，则定义每个桶的大小的数组长度(最大)
    int[][] bucket = new int[10][arr.length];
    //为了记录每个桶里所放元素个数，定义一个一维数组，记录各个桶的每次放入的数据个数
    //bucketElementCounts[0]记录的就是bucket[0]这个桶 每次放入数据的个数
    int[] bucketElementCounts = new int[10];//记录10个桶，每个桶的数据的个数
    //得到数组中最大的数
    int max = arr[0];//先假设第一个数是最大的
    for (int i = 1; i < arr.length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }
    //得到最大值 max的位数
    int maxLength = (Math.abs(max) + "").length();
    for (int i = 0, n = 1; i < maxLength; i++, n*= 10) {
        //第i轮，针对每个元素的对应位进行排序处理，第1次：个位；第2次：十位
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的对应位
            int digitOfElement = arr[j] / n % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;//一个桶放入一个元素后，要递增
        }
        //按照桶里的元素顺序，（即一维数组的下标）依次取出数据，放入原来的数组
        int index = 0;
        //遍历每个桶，并将桶中数据，放入原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中有数据，才将其数据放入原数组，如果桶里没有数据，则不用放
            if (bucketElementCounts[k] != 0) {//k桶才有数据
                //循环该桶，即第k个桶（第k个一维数组）
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素，放入到arr[]数组
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //做完后，要把桶置零，bucketElements[k] = 0 !!!!!!!!!!
            bucketElementCounts[k] = 0;
        }
        //结果
        System.out.println("第" + (i+1) + "轮，对个位的排序处理： arr = " + Arrays.toString(arr));
    }
}