java算法基数排序

基数排序&＃xff08;英语&＃xff1a;Radix sort&＃xff09;是一种非比较型整数排序算法&＃xff0c;其原理是将整数按位数切割成不同的数字&＃xff0c;然后按每个位数分别比较。由于整数也可以表达字符串&＃xff08;比如名字或日期&＃xff09;和特定格式的浮点数&＃xff0c;所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机&＃xff08;Tabulation Machine&＃xff09;上的贡献[1]。

它是这样实现的&＃xff1a;将所有待比较数值&＃xff08;正整数&＃xff09;统一为同样的数字长度&＃xff0c;数字较短的数前面补零。然后&＃xff0c;从最低位开始&＃xff0c;依次进行一次排序。这样从最低位排序一直到最高位排序完成以后&＃xff0c;数列就变成一个有序序列。

import java.util.Arrays;public class RadixSort {public int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝&＃xff0c;不改变参数内容int[] arr &＃61; Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit &＃61; getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue &＃61; getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue &＃61; arr[0];for (int value : arr) {if (maxValue }


运行结果&＃xff1a;

1 2 3 4 4 5 5 6 7 8 15 17 22