基数算法的思路是数组中的元素无论是几位数,但是每一位都不可能超过0-9的范围,所以通过循环判断每一位属于0-9的哪一个.将其放入对应的栈中,一次循环下来,确定了个位数的排序.如果是两个元素在同一个栈中那取出的顺序是先进先出.第二次循环确定十位的位置
第三次是百位以此类推.这里需要注意的是最大的循环次数应该是数组中最大元素的位数,所以如果发现位数不相同需要补0
public static void jishu(int[] arr) {
//将数组转换成字符串数组,并找到最长的数
String[] sarr = new String[arr.length];
int max = 1;
for (int i = 0; i < arr.length; i++) {
String s = String.valueOf(arr[i]);
sarr[i] = s;
if (s.length() > max) {
max = s.length();
}
}
for (int i = 0; i < sarr.length; i++) {
int c = max - sarr[i].length();
for (int x = 0; x < c; x++) {
sarr[i] = "0" + sarr[i];
}
}
Queue queue0 = new ArrayDeque<>();
Queue queue1 = new ArrayDeque<>();
Queue queue2 = new ArrayDeque<>();
Queue queue3 = new ArrayDeque<>();
Queue queue4 = new ArrayDeque<>();
Queue queue5 = new ArrayDeque<>();
Queue queue6 = new ArrayDeque<>();
Queue queue7 = new ArrayDeque<>();
Queue queue8 = new ArrayDeque<>();
Queue queue9 = new ArrayDeque<>();
for (int i = max - 1; i >= 0; i--) {
for (int x = 0; x < sarr.length; x++) {
String s = sarr[x].charAt(i) + "";
switch (s) {
case "0":
queue0.add(sarr[x]);
break;
case "1":
queue1.add(sarr[x]);
break;
case "2":
queue2.add(sarr[x]);
break;
case "3":
queue3.add(sarr[x]);
break;
case "4":
queue4.add(sarr[x]);
break;
case "5":
queue5.add(sarr[x]);
break;
case "6":
queue6.add(sarr[x]);
break;
case "7":
queue7.add(sarr[x]);
break;
case "8":
queue8.add(sarr[x]);
break;
case "9":
queue9.add(sarr[x]);
break;
}
}
int index = 0;
while (!queue0.isEmpty()) {
sarr[index] = queue0.poll();
index++;
}
while (!queue1.isEmpty()) {
sarr[index] = queue1.poll();
index++;
}
while (!queue2.isEmpty()) {
sarr[index] = queue2.poll();
index++;
}
while (!queue3.isEmpty()) {
sarr[index] = queue3.poll();
index++;
}
while (!queue4.isEmpty()) {
sarr[index] = queue4.poll();
index++;
}
while (!queue5.isEmpty()) {
sarr[index] = queue5.poll();
index++;
}
while (!queue6.isEmpty()) {
sarr[index] = queue6.poll();
index++;
}
while (!queue7.isEmpty()) {
sarr[index] = queue7.poll();
index++;
}
while (!queue8.isEmpty()) {
sarr[index] = queue8.poll();
index++;
}
while (!queue9.isEmpty()) {
sarr[index] = queue9.poll();
index++;
}
}
for (int i = 0; i < sarr.length; i++) {
arr[i] = Integer.valueOf(sarr[i]);
}
}
以下是一个测试方法
Original: https://www.cnblogs.com/zumengjie/p/16183966.html
Author: 顶风少年
Title: 数据结构与算法之基数算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588893/
转载文章受原作者版权保护。转载请注明原作者出处！