基本思路：先找出数组中最大的数，确定好位数来确定需要排序多少次。然后从个位开始进行归类，个位数一样的放在同一个桶里（桶的排序为 0-9 依次排序），然后按从左到右，从底到上的顺序取出。个位 - 十位 - 百位...... 依次类推，最终排序完成。
注意：不能从位数大的向位数小的开始排序，只能从位数小的向位数大的开始排序。因为位 数大的排好序之后，位数小的可能会打乱顺序。
步骤：1. 取出数组中最大的数，并取得位数；
2. 根据位数把数组中的数都放在桶里
3. 把分类好的元素取出来
4. 把排好序的元素与原始数组元素一一对应交换
平均时间复杂度：O（n*k）
import java.util.Arrays; public class RedixSort { public static void main(String[] args) { int[] arr = {3, 45, 78, 99, 45, 11, 3564, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49}; System.out.println("未排序数组："+ Arrays.toString(arr)); redixSort(arr); System.out.println("已排序数组："+Arrays.toString(arr)); } /** * 1)基数排序时对传统桶排序的扩展，速度很快。 * 2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法 */ public static void redixSort(int[] arr){ int[][] bucket = new int[10][arr.length-1]; //桶里面存的具体数值，一维是每个桶，二维是桶里面 int[] bucketElementCounts = new int[10];//每个桶所存的元素个数 int max = arr[0]; for (int i = 0;i < arr.length;i++){//找出最大数，根据最大数有多少位数来确定排序次数 if (max < arr[i]){ max = arr[i]; } } int maxCount = (max + "").length();//将数字变为字符串，方便进行拆分 for (int i= 0;i < maxCount;i++){ //把数组中的数都在放在桶里 for (int k =0;k < arr.length;k++){ int value = (arr[k] / (int) Math.pow(10,i)) % 10;//计算出每个位数 bucket[value][bucketElementCounts[value]] = arr[k];//bucket[7][0] = arr[k]; bucketElementCounts[value]++; } int index = 0; for (int k = 0;k < bucketElementCounts.length;k++){//遍历每个桶 if (bucketElementCounts[k] != 0){ for (int x = 0;x < bucketElementCounts[k];x++){//遍历每个桶的元素 arr[index] = bucket[k][x]; index++; } } bucketElementCounts[k] = 0; } } } }
