基数排序属于“分配式排序”，又称桶子排序法，是一种稳定的排序算法。
基本操作：先找出数据最大的位数，然后按照从低位（从高位）开始排序，收集已排序的数据，直到最高位（最低位）排序完成。
例如：先个位排序，再十位排序，然后依次是百位、千位，直到最高位。
备注：基数排序有高位优先排序（简称MSD），和低位优先排序（简称LSD）两种排序方式。
二）算法原理
基础原理：
第一步：先计算出数据的最大位数（最大长度）。
第二步：先从低位（高位）开始排序，收集已排序的数据，再从高位（低位）开始排序，收集已排序的数据。
第三步：不断从低位到高位（从高位到低位），对数据进行排序，直到最高位（最低位）已排好，排序完成。
算法步骤图解：
LSD静态图：（先个位排序、再十位排序、再百位排序）
LSD动态图：（先个位排序、再十位排序、再百位排序）
算法复杂度：
最差情况：T(n) = O(n*k)
最好情况：T(n) = O(n*k)
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n * k)，其中k是整数的范围。
三）数字基数排序
数字基数排序原理：
第一步： 先计算出数据中数字的最大位数。
第二步：先从个位开始，根据个位数大小，把数据依次从小到大排序。
第三步：再从十位开始，根据十位数大小，把数据依次从小到大排序。
第四步：再从百位、千位、计算对应位数的数据大小，一直到最高位的数据排序完成，才结束。
数字基数排序源码：
/** * 数字基数排序 * @param arr * @return */public static int[] radixSort(int[] nums) {if(nums == null) {return null;}int digit = 0; // 先默认只有0位int maxDigit = 0; // 只记录最大的位数// 先获取数组的最大位数for (int i = 0; i < nums.length; i++) {int number = nums[i];while (number > 0) {number = number/10;digit++;}// 只记录最大的位数maxDigit = Math.max(maxDigit, digit);digit = 0; // 初始化}ArrayList<ArrayList<Integer>> buckets = null;// 根据位数排序for (int i = 0; i < maxDigit; i++) {// 因为数字只有0到9总共10个,所以声明10个桶buckets = new ArrayList<ArrayList<Integer>>();for (int b = 0; b < 10; b++) {buckets.add(new ArrayList<Integer>());}// 排序,主要需要考虑到桶的容量,比如数组为10个桶,字母26个桶int base = (int) Math.pow(10, i);for (int a : nums) {int index = a / base % 10; // 该步骤是为了获取最后一位数buckets.get(index).add(a); // 把最后一位一样的值分配到一个桶}int index = 0;for (ArrayList<Integer> bucket : buckets) {for (int b : bucket) {nums[index++] = b;}}}return nums;}四）英文字母排序
英文字母排序原理：
第一步：先计算出数据中字符串最大长度。
第二步：从首字母开始排序，把字母转换成数字，相当于对数字进行排序。
第三步：继续下一个字母排序，直到最后一个字母排序完成。
备注：如果字符串超长，可能性能耗时会多一点。
英文字母排序源码：
/** * 字符串基数排序 * @param strArr * @return */public static String[] stringRadixSort(String[] strArr) {if(strArr == null) {return null;}int maxLength = 0; // 只记录最大的位数// 先获取数组的最大位数for (String len : strArr) {// 只记录最大的位数if (len.length() >= maxLength) {maxLength = len.length();}}System.out.println("字符串基数排序中字符串最大长度为: " + maxLength);ArrayList<ArrayList<String>> buckets = null;// 从最后一个字母开始排序for (int i=maxLength-1; i>=0; i--) {// 因为英文字母只有26个,所以声明26个桶buckets = new ArrayList<ArrayList<String>>();for (int b = 0; b < 27; b++) {buckets.add(new ArrayList<String>());}// 排序,主要需要考虑到桶的容量,比如数组为10个桶,字母26个桶for (String str : strArr) {buckets.get(getStrIndex(str, i)).add(str);}// 重新赋值int index = 0;for (ArrayList<String> bucket : buckets) {for (String str : bucket) {strArr[index++] = str;}}}return strArr;}public static int getStrIndex(String str, int charIndex) { if (charIndex >= str.length()) {return 0; // 第 0 个桶存非字母情况} int index = 26; // 总共26个字母int n = (int) str.charAt(charIndex); // 把字母强制转换成数字if (64 < n && n < 91) { // 大写字母区间范围index = n - 64;} else if (96 < n && n < 123) { // 小写字母区间范围index = n - 96;} else {// 把其余非字母的排最后index = 26;}return index;}
识别二维码关注个人微信公众号
本章完结，待续，欢迎转载！
本文说明：该文章属于原创，如需转载，请标明文章转载来源！