基数排序

基本说明图示代码

基本说明

基数排序（radixsort）属于“分配式排序”（distributionsort），又称“桶子法”（bucketsort）或binsort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法基数排序(RadixSort)是桶排序的扩展

图示

代码

public class RadixSort { public static void main(String[] args) { int[] arr = {53,3,542,748,14,214}; //1、得到数组中最大数的位数 int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max){ max = arr[i]; } } int maxLength = (max + "").length(); //最大数的位数 //2、声明一个二维数组，表示10个桶 int[][] bucket = new int[10][arr.length];//典型的空间换时间 int[] bucketCounts = new int[10];//记录每一个桶存放的数据 //3、将数据存入桶中 for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { for (int j = 0; j < arr.length; j++) { int digit = arr[j] / n % 10;//取出每个元素对应为的值 //放入桶中 bucket[digit][bucketCounts[digit]] = arr[j]; // System.out.print("bucket[" + digit + "][" + bucketCounts[digit]+"] = " + bucket[digit][bucketCounts[digit]] + "\t"); bucketCounts[digit]++; } //4、按照桶的顺序放入原来数组 int index = 0; for (int a = 0; a < bucketCounts.length; a++) { if (bucketCounts[a] != 0){//桶中有数据 for (int b = 0; b < bucketCounts[a]; b++) { arr[index] = bucket[a][b]; index++; } } bucketCounts[a] = 0;//需将桶置零 } System.out.println("\n第" + (i + 1) + "轮排序：" + Arrays.toString(arr)); } } }

【结果】