5.3基數排序
基數排序的用途在于對相同位數的編号進行排序，例如學号，商品編碼
下面展示的是書中的僞代碼：
RADIXSORT
輸入：一張有n個數的表L={a1,a2,a3....,an}和k位數字。
輸出：按非降序排序的L
1.for j <- 1 to k
2. 準備10個空表L0,L1,...,L9
3. while L 非空
4. a <- L中的下一個元素;删除a。 //将L中的數配置設定到10個表
5. i <- a中的第j位數字了；将a加入表Li中
6. end while
7. L <- L0 //L0加入到L
8. for i <- 1 to 9
9. L <- L,Li
10. end for
11.end for
12.return L
上傳代碼之前先述說自己遇到的問題：
- 第一坑，求個十百千位時，原以為隻用一個%号就足夠了，後來發現每一位的公式都不太一樣，具體，而且剛開始寫的時候，直接用的10^j，那不是1234求十位就是1234%100=34，是以j是要去減1的，而且不能隻用%
for (int j = 1; j <= k; j++) {
while (L != null && L.size() != 0) {
a = L.get(0);
L.remove(0);
if (j==1){
i = (int) (a % Math.pow(10, j));
}else if(j==2){
i = (int) (a / Math.pow(10, j-1)%10);
}else if(j==k){
i = (int) (a / Math.pow(10, j-1));
}else {
i = (int) (a / Math.pow(10, j-1)%10);
}
- 第二坑，僞代碼8，9行，把L0,L1,…L9合并到L中之後是要清空L0,L1,…L9的，這一點僞代碼中并沒有寫到，鬼知道我debug了多久，排序十位的時候，發現我明明存入一個數到L3，L3中怎麼會出現3個數，才發覺是不是排序個位的時候L3合并到L之後沒有清空導緻原來的數字還存在着
for (int b = 0; b <= 9; b++) {
switch (b) {
case 0:
L.addAll(L0);
L0.removeAll(L0);
break;
case 1:
L.addAll(L1);
L1.removeAll(L1);
break;
case 2:
L.addAll(L2);
L2.removeAll(L2);
break;
case 3:
L.addAll(L3);
L3.removeAll(L3);
break;
case 4:
L.addAll(L4);
L4.removeAll(L4);
break;
case 5:
L.addAll(L5);
L5.removeAll(L5);
break;
case 6:
L.addAll(L6);
L6.removeAll(L6);
break;
case 7:
L.addAll(L7);
L7.removeAll(L7);
break;
case 8:
L.addAll(L8);
L8.removeAll(L8);
break;
case 9:
L.addAll(L9);
L9.removeAll(L9);
break;
}
}
- 第三坑，僞代碼中4，5行，取出L中的下一個元素，于是我就用了一個for循環，但是每取出一個數，你是要從list中删除一個數的，就會導緻你的u=0的時候，數組原來是8個，你取出的的确是第一個，但是新數組現在是7個，你u++之後，u=1了，就會從新數組取出第二個數，導緻結果出錯，我的解決方法是直接取0，删除一個之後不斷取0删除0，那麼就會總取第一個了
a = L.get(0);
L.remove(0);
下面展示的是Java的實作：
package com.sheye;
import java.util.ArrayList;
import java.util.List;
/**
* @author Sheye
* @date 2019-10-15 17:23
*/
public class RadixSort {
static int a;
static List<Integer> L = new ArrayList();
static List<Integer> L0 = new ArrayList();
static List<Integer> L1 = new ArrayList();
static List<Integer> L2 = new ArrayList();
static List<Integer> L3 = new ArrayList();
static List<Integer> L4 = new ArrayList();
static List<Integer> L5 = new ArrayList();
static List<Integer> L6 = new ArrayList();
static List<Integer> L7 = new ArrayList();
static List<Integer> L8 = new ArrayList();
static List<Integer> L9 = new ArrayList();
static void radixSort(int k) {
int i;
L.add(7467);
L.add(1247);
L.add(3275);
L.add(6792);
L.add(9187);
L.add(9134);
L.add(4675);
L.add(1239);
// for (int i :L) {
// System.out.println(i);
// }
for (int j = 1; j <= k; j++) {
while (L != null && L.size() != 0) {
//for (int u = 0; u < L.size(); u++) {
a = L.get(0);
L.remove(0);
if (j==1){
i = (int) (a % Math.pow(10, j));
}else if(j==2){
i = (int) (a / Math.pow(10, j-1)%10);
}else if(j==k){
i = (int) (a / Math.pow(10, j-1));
}else {
i = (int) (a / Math.pow(10, j-1)%10);
}
switch (i) {
case 0:
L0.add(a);
break;
case 1:
L1.add(a);
break;
case 2:
L2.add(a);
break;
case 3:
L3.add(a);
break;
case 4:
L4.add(a);
break;
case 5:
L5.add(a);
break;
case 6:
L6.add(a);
break;
case 7:
L7.add(a);
break;
case 8:
L8.add(a);
break;
case 9:
L9.add(a);
break;
}
//}
}
for (int b = 0; b <= 9; b++) {
switch (b) {
case 0:
L.addAll(L0);
L0.removeAll(L0);
break;
case 1:
L.addAll(L1);
L1.removeAll(L1);
break;
case 2:
L.addAll(L2);
L2.removeAll(L2);
break;
case 3:
L.addAll(L3);
L3.removeAll(L3);
break;
case 4:
L.addAll(L4);
L4.removeAll(L4);
break;
case 5:
L.addAll(L5);
L5.removeAll(L5);
break;
case 6:
L.addAll(L6);
L6.removeAll(L6);
break;
case 7:
L.addAll(L7);
L7.removeAll(L7);
break;
case 8:
L.addAll(L8);
L8.removeAll(L8);
break;
case 9:
L.addAll(L9);
L9.removeAll(L9);
break;
}
}
for (Integer list:L) {
System.out.print(list+",");
}
System.out.println();
}
}
public static void main (String[]args){
// System.out.println("請輸入一個數字");
// Scanner sc = new Scanner(System.in);
// String str = sc.next();
// System.out.println("排序後的結果");
radixSort(4);
}
}
貼上運作結果
每一次循環排序的結果如下：
6792,9134,3275,4675,7467,1247,9187,1239,
9134,1239,1247,7467,3275,4675,9187,6792,
9134,9187,1239,1247,3275,7467,4675,6792,
1239,1247,3275,4675,6792,7467,9134,9187,
總結：我真的太水了，自認為自己不錯，這麼簡單的一個代碼，幾乎是從下午5點做到了晚上10點，我有什麼用？還有就是基本完成了實作，我是測試的時候直接給上數的位數的，但是可以添加一個scanner，輸入你輸入的是個幾位數，也可以直接從數組中取出一個數，然後轉化為字元串，用STRING裡面的length方法，檢視是幾位數，再帶入到實參中去，以後套用的時候也可以封裝成面向對象，更好調用。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)