基数排序
没有递归的规则,很好理解,取决你最大数的位数.
一定注意每进行一次桶排序,都要将桶里面的值清空
package com.ywystu.SortType;import java.util.Arrays;/*** @author 是狸猫啊！* @Version 1.0*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = {
53, 3, 542, 748, 14, 214};//RadixSort(arr);radixall(arr);}//使用基数排序//1.二维数组包含十个一维数组//2.为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length//3.基数排序是很经典的用空间换时间的算法public static void RadixSort(int[] arr) {
int[][] bucket = new int[10][arr.length];//定义一个数组 提示我们实际上每一个桶中实际存放了多少的数据int[] bucketElementCounts = new int[10];//这是第一轮的排序for (int j = 0; j < arr.length; j++) {
//取出每一个元素的个位的数值int digitoOfElement = arr[j] % 10;//这下开始往桶里面放数bucket[digitoOfElement][bucketElementCounts[digitoOfElement]] = arr[j];bucketElementCounts[digitoOfElement]++;}//按照每一个桶的顺序.int index = 0;for (int i = 0; i < bucket.length; i++) {
if (bucketElementCounts[i] == 0) {
continue;}for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];index++;}bucketElementCounts[i] = 0;//第一轮处理后 ,就需要将 if (bucketElementCounts[i] != 0) {
for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];
index++;
}
}
// //第一轮处理后 ,就需要将
// bucketElementCounts[i] = 0;}System.out.println("排序后的结果arr = " + Arrays.toString(arr));//这是第二轮的排序for (int j = 0; j < arr.length; j++) {
//取出每一个元素的个位的数值int digitoOfElement = arr[j] / 10 % 10;//这下开始往桶里面放数bucket[digitoOfElement][bucketElementCounts[digitoOfElement]] = arr[j];bucketElementCounts[digitoOfElement]++;}//按照每一个桶的顺序.index = 0;for (int i = 0; i < bucket.length; i++) {
if (bucketElementCounts[i] == 0) {
continue;}for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];index++;}bucketElementCounts[i] = 0;}System.out.println("排序后的结果arr = " + Arrays.toString(arr));//这是第三轮的排序for (int j = 0; j < arr.length; j++) {
//取出每一个元素的个位的数值int digitoOfElement = arr[j] / 100 % 10;//这下开始往桶里面放数bucket[digitoOfElement][bucketElementCounts[digitoOfElement]] = arr[j];bucketElementCounts[digitoOfElement]++;}//按照每一个桶的顺序.index = 0;for (int i = 0; i < bucket.length; i++) {
if (bucketElementCounts[i] == 0) {
continue;}for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];index++;}bucketElementCounts[i] = 0;}System.out.println("排序后的结果arr = " + Arrays.toString(arr));}//一次性循环的结果public static void radixall(int[] arr) {
//对位数进行循环校验和读取int max = arr[0];for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];}}System.out.println("max的值=" + max);int maxlength = (max + "").length();int[][] bucket = new int[10][arr.length];//定义一个数组 提示我们实际上每一个桶中实际存放了多少的数据int[] bucketElementCounts = new int[10];//这是第一轮的排序for (int k = 0, n = 1; k < maxlength; k++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//取出每一个元素的个位的数值int digitoOfElement = arr[j] / n % 10;//这下开始往桶里面放数bucket[digitoOfElement][bucketElementCounts[digitoOfElement]] = arr[j];bucketElementCounts[digitoOfElement]++;}//按照每一个桶的顺序.int index = 0;for (int i = 0; i < bucket.length; i++) {
if (bucketElementCounts[i] == 0) {
continue;}for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];index++;}bucketElementCounts[i] = 0;}System.out.println("排序后的结果arr = " + Arrays.toString(arr));}}
}