基数排序-Java面试指南

当前位置:　首页>> 技术小册>> Java面试指南

基数排序（Radix Sort）是一种非比较排序算法，它按照个位、十位、百位...的顺序依次对待排序元素进行排序。接下来，我将为您提供使用Java语言实现基数排序的代码和说明。

代码如下：

```java
import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = { 53, 89, 150, 36, 633, 233, 71, 66, 322 };
        System.out.println("Original array: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

public static void radixSort(int[] arr) {
        // 找到最大数，确定要排序几次
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int count = 0;
        while (max > 0) {
            max /= 10;
            count++;
        }

// 创建桶
        int[][] bucket = new int[10][arr.length];

// 记录每个桶中实际存放的数据个数
        int[] bucketElementCount = new int[10];

// 对每一位进行排序，从个位开始
        for (int i = 0, n = 1; i < count; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
                bucketElementCount[digitOfElement]++;
            }

// 将桶中的数据取出来放回原数组
            int index = 0;
            for (int k = 0; k < bucketElementCount.length; k++) {
                if (bucketElementCount[k] != 0) {
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                    bucketElementCount[k] = 0;
                }
            }
        }
    }
}
```

在这个实现中，我们使用桶来存储排序元素，桶的个数为10，分别代表数字0-9。在排序的过程中，我们先找到要排序的元素中的最大值，然后确定需要排序的次数。对于每一次排序，我们按照从低位到高位的顺序，将元素存储到对应的桶中，最后将桶中的元素按照顺序取出，放回原数组。

该分类下的相关小册推荐：

Java语言基础7-Java中的异常

Java并发编程实战

Java语言基础16-JDK8 新特性

Mybatis合辑2-Mybatis映射文件

Mybatis合辑1-Mybatis基础入门

Java必知必会-Maven高级

Java语言基础4-数组详解

Java语言基础3-流程控制

Mybatis合辑5-注解、扩展、SQL构建

java源码学习笔记

Java语言基础2-运算符

深入理解Java虚拟机