基数排序推导过程和最终算法

本文主要是介绍基数排序推导过程和最终算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

推导过程：

package indi.tom.Algorithm.recursion.sort;import java.util.Arrays;/*** @Author Tom* @Date 2019/11/11 19:36* @Version 1.0* @Description 基数排序，空间换时间.这里列出推导过程。在RadixSortFinal中给出最终方法。*/
public class RadixSort {public static void main(String[] args) {int[] array = {53,3,542,748,14,214};radixSort(array);}//基数排序public static void radixSort(int[] array){//推导过程//第一轮//定义一个二维数组，充当桶int[][] buckets = new int[10][array.length];//定义一个数组，下标代表第几个桶，值对应该桶中的元素个数。int[] elementsCountInBucket = new int[10];//遍历数组元素，按个位数加到对应的每一个桶中for (int i = 0; i < array.length; i++) {int digitOfElement = array[i] % 10;buckets[digitOfElement][elementsCountInBucket[digitOfElement]] = array[i];elementsCountInBucket[digitOfElement] ++;}//将桶中元素重新放回原数组。int current = 0;//定义原数组的当前下标。for (int i = 0; i < buckets.length; i++) {if(elementsCountInBucket[i] > 0){for (int j = 0; j < elementsCountInBucket[i]; j++) {array[current++] = buckets[i][j];}}//将保存每个bucket元素个数的元素清零。elementsCountInBucket[i] = 0;}System.out.println(Arrays.toString(array));//第二轮//遍历数组元素，按个位数加到对应的每一个桶中for (int i = 0; i < array.length; i++) {int digitOfElement = array[i] /10 % 10;buckets[digitOfElement][elementsCountInBucket[digitOfElement]] = array[i];elementsCountInBucket[digitOfElement] ++;}//将桶中元素重新放回原数组。current = 0;//定义原数组的当前下标。for (int i = 0; i < buckets.length; i++) {if(elementsCountInBucket[i] > 0){for (int j = 0; j < elementsCountInBucket[i]; j++) {array[current++] = buckets[i][j];}}elementsCountInBucket[i] = 0;}System.out.println(Arrays.toString(array));//第三轮for (int i = 0; i < array.length; i++) {int digitOfElement = array[i] /100 % 10;buckets[digitOfElement][elementsCountInBucket[digitOfElement]] = array[i];elementsCountInBucket[digitOfElement] ++;}//将桶中元素重新放回原数组。current = 0;//定义原数组的当前下标。for (int i = 0; i < buckets.length; i++) {if(elementsCountInBucket[i] > 0){for (int j = 0; j < elementsCountInBucket[i]; j++) {array[current++] = buckets[i][j];}}elementsCountInBucket[i] = 0;}System.out.println(Arrays.toString(array));}
}

最终结果：

package indi.tom.Algorithm.recursion.sort;import java.util.Arrays;/*** @Author Tom* @Date 2019/11/11 19:36* @Version 1.0* @Description 基数排序，最终方法*/
public class RadixSortFinal {public static void main(String[] args) {int[] array = {53,3,542,748,14,214};radixSort(array);}//排序函数public static void radixSort(int[] array){//定义一个二维数组，充当桶int[][] buckets = new int[10][array.length];//定义一个数组，下标代表第几个桶，值对应该桶中的元素个数。int[] elementsCountInBucket = new int[10];//要检查的元素的某一位上的数字int digitOfElement;//找出给定数组的最大数，以便下一步算出该最大数的位数int max = array[0];for (int i = 0; i < array.length; i++) {if(max < array[i]){max = array[i];}}//算出数组中最大数有多少位数字，即是我们要做多少轮入桶，出桶的过程int numberOfDigits = (max + "").length();for (int i = 0; i < numberOfDigits; i++) {//遍历数组元素，按个位数加到对应的每一个桶中for (int j = 0; j < array.length; j++) {digitOfElement = array[j] / (int)Math.pow(10, i) % 10;buckets[digitOfElement][elementsCountInBucket[digitOfElement]] = array[j];elementsCountInBucket[digitOfElement] ++;}//将桶中元素重新放回原数组。int current = 0;//定义原数组的当前下标。for (int j = 0; j < buckets.length; j++) {if(elementsCountInBucket[j] > 0){for (int k = 0; k < elementsCountInBucket[j]; k++) {array[current++] = buckets[j][k];}}//将保存每个bucket元素个数的元素清零。elementsCountInBucket[j] = 0;}}System.out.println(Arrays.toString(array));}
}

 

 

这篇关于基数排序推导过程和最终算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---