基数排序的代码实现（LSD的基数排序[最低位优先，适用于位数小的数列]，java语言）
思想（来自百度百科）
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
实现代码
import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;/ * className:Sort * * @author:zjl * @version:0.1 * @date:2020/8/1820:09 * @since:jdk1.8 */public class Sort { //测试 public static void main(String[] args) { int R[] = {159, 36, 999, 564, 852, 4444, 695, 3}; int[] ints = radixSort(R); for (int i = 0; i < ints.length; i++) { System.out.print(R[i] + " "); } } public static int[] radixSort(int[] R) { //获取数组R中最大数的位数 int maxDigit = getDigit(R); //利用队列先进先出的特性 模拟桶 Queue<Integer> bucket0 = new LinkedList<>(); Queue<Integer> bucket1 = new LinkedList<>(); Queue<Integer> bucket2 = new LinkedList<>(); Queue<Integer> bucket3 = new LinkedList<>(); Queue<Integer> bucket4 = new LinkedList<>(); Queue<Integer> bucket5 = new LinkedList<>(); Queue<Integer> bucket6 = new LinkedList<>(); Queue<Integer> bucket7 = new LinkedList<>(); Queue<Integer> bucket8 = new LinkedList<>(); Queue<Integer> bucket9 = new LinkedList<>(); for (int j = 0; j < maxDigit; j++) { //共需要进行maxDigit次进桶出桶操作 for (int i = 0; i < R.length; i++) { int k; String s = String.valueOf(R[i]); char[] chars = s.toCharArray(); if (chars.length - j - 1 < 0) //如果R[i]该位上没有数字 k = 0; //相当于高位补0操作 else k = Integer.parseInt(String.valueOf(chars[chars.length - j - 1]));//将R[i]该位上的树字赋值给k// System.out.println(k + "->" + R[i]); switch (k) { //根据k的值将R[i]放入相应桶中 case 0: bucket0.offer(R[i]); break; case 1: bucket1.offer(R[i]); break; case 2: bucket2.offer(R[i]); break; case 3: bucket3.offer(R[i]); break; case 4: bucket4.offer(R[i]); break; case 5: bucket5.offer(R[i]); break; case 6: bucket6.offer(R[i]); break; case 7: bucket7.offer(R[i]); break; case 8: bucket8.offer(R[i]); break; case 9: bucket9.offer(R[i]); break; } } //从0号桶——>9h号桶依次出桶（先进先出） int index = -1; while (!bucket0.isEmpty()) { index++; R[index] = bucket0.poll(); } while (!bucket1.isEmpty()) { index++; R[index] = bucket1.poll(); } while (!bucket2.isEmpty()) { index++; R[index] = bucket2.poll(); } while (!bucket3.isEmpty()) { index++; R[index] = bucket3.poll(); } while (!bucket4.isEmpty()) { index++; R[index] = bucket4.poll(); } while (!bucket5.isEmpty()) { index++; R[index] = bucket5.poll(); } while (!bucket6.isEmpty()) { index++; R[index] = bucket6.poll(); } while (!bucket7.isEmpty()) { index++; R[index] = bucket7.poll(); } while (!bucket8.isEmpty()) { index++; R[index] = bucket8.poll(); } while (!bucket9.isEmpty()) { index++; R[index] = bucket9.poll(); } } return R; } //获取一个数组最大的数字的最高位数 public static int getDigit(int R[]) { int maxDigit = 0; for (int i = 0; i < R.length; i++) { int length = String.valueOf(R[i]).length(); if (length > maxDigit) maxDigit = length; } return maxDigit; }}测试结果
