11、数据结构与算法 - 实战:排序算法之基数排序

1、基本思想

把待排序序列的数值统一为同样的数位长度,数位较短的数字在前面补零。然后从最低位开始,依此进行依此排序。这样从最低位排序一直到最高位排序完成后,数列就变成一个有序序列。
基数排序属于分配式排序,又称桶子法。

2、图解

假设存在10个桶,分别为0-9号桶。
 
假设待排序序列为:{64,8,216,512,27,729,000,001,343,125}
首先把数值统一为同样的长度:{064,008,216,512,027,729,000,001,343,125}
然后从最低位开始,依此进行依此排序。
第一轮,遍历序列,依次把数值放置到和个位数相同的编号的桶当中。
 
然后按照桶编号依次拿出数字:{000,001,512,343,064,125,216,027,008,729}
第二轮,遍历第一轮结束的序列,依次把数值放置到和十位数相同的编号的桶当中。
 
然后按照桶的编号依次拿出数字:{000,001,008,512,216,125,027,729,343,064}
第三轮,遍历第二轮结束的序列,依次把数值放置到和百位数相同的编号的桶当中。
 
然后按照桶的编号依次拿出数字:{000,001,008,027,064,125,216,343,512,729}。
最大数字对应字符串长度位3,所以执行3轮就排序好了。

3、代码实现

package cn.klb.datastructures.sort;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 实现数组的基数排序(桶子法)
 * @Date: Create in 2023/4/5 15:06
 * @Modified By:
 */
public class Radix {
   
     

    public static void sort(int[] arr) {
   
     
        // 找到待排序序列最大的数字
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
   
     
            if (max < arr[i]) {
   
     
                max = arr[i];
            }
        }

        // 获取最大数字的对应字符串长度
        int maxLength = ("" + max).length();

        // 定义一个二维数组代表所有桶
        // 比如:bucket[0] 表示0号桶
        int[][] bucket = new int[10][arr.length];

        // 定义一个一维数组保存每个桶元素的数量
        // 比如:elementNums[2] == 3 表示2号桶有3个元素
        int[] elementNums = new int[10];

        // 桶的序号 0~9
        int no = 0;

        // 元素从桶里放回数组时用到
        int index = 0;

        // i == {0,1,2,...,maxLength} 分别表示个、十、百...
        for (int i = 0; i < maxLength; i++) {
   
     
            // arr数组每个元素放到指定的桶里
            for (int j = 0; j < arr.length; j++) {
   
     
                no = (int) (arr[j] / Math.pow(10, i) % 10);
                bucket[no][elementNums[no]++] = arr[j];
            }
            // 每个桶里的元素按顺序覆盖回原数组
            for (int k = 0; k < 10; k++) {
   
     
                for (int count = 0; count < elementNums[k]; count++) {
   
     
                    arr[index++] = bucket[k][count];
                }
                elementNums[k] = 0; // 放好了存量就为0
            }
            // 执行完一轮后,执行清零操作
            index = 0;
        }
    }
}

4、时间复杂度

代码中的基数排序不能排序负数,若要排序负数,得进行附加操作,但是原理是不变的。基数排序的一个应用是将字符串排序。
一般来说,在第k轮后,元素按第k低位有序,所以运行结束后所有元素就完全有序了。运行时间是O(p(n+b)),其中p是轮数,n是待排序元素个数,b是桶的个数。

5、稳定性

元素装入桶的顺序和从桶里倒出来的顺序是不变的,因此,相同元素的前后顺序不会发生改变,因此基数排序是稳定的。

6、测试

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.sort.*;
import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 排序测试
 * @Date: Create in 2023/4/3 21:32
 * @Modified By:
 */
public class SotrTest {
   
     
    @Test
    public void testRadix(){
   
     
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
   
     
            arr[i] = (int) (Math.random() * 80000000);
        }
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = new Date();
        System.out.println("-----" + sdf.format(date1) + "-----");
        //System.out.println(Arrays.toString(arr));

        Radix.sort(arr);

        Date date2 = new Date();
        System.out.println("-----" + sdf.format(date2) + "-----");
        //System.out.println(Arrays.toString(arr));
        // 800万的随机数据进行基数排序,我的电脑花了大约2秒(测不了8000万,内存炸了)
    }
}