看見過c++遏佣，c#解此題，未見java揽浙，寄己寫一篇状婶，加深印象。
算法題之前理清思路馅巷。關(guān)鍵點(diǎn)： 基數(shù)排序
-
準(zhǔn)備工作：
1 :根據(jù)最大長度（MaxLen）把單詞都最后補(bǔ)位成空格填充尾部至MaxLen長的單詞膛虫。比如“abdd”“abd”。則“abdd”“abd ”钓猬。
2:弄27個桶稍刀，第一個桶對應(yīng)“ ”，另外26個桶對應(yīng)26個字母敞曹；
3:每個桶用隊列的形式存儲账月。(用LinkedNode需準(zhǔn)備兩個LinkedNode[] 一個存頭，一個用于往鏈表加元素)
-
排序：
按關(guān)鍵字的第j（從MaxLen-1到0）個分量進(jìn)行分配（進(jìn)入此過程時各隊列一定為空）异雁，依次將各非空隊列中的記錄收集起來捶障，循環(huán)到第0個分量
-
結(jié)束工作：
恢復(fù)處理僧须，刪除預(yù)處理時填充的尾部空格纲刀。
輸出。
-
代碼
public class Sort{
class LinkedNode {
private Object value;
private LinkedNode next;
public LinkedNode(Object value, LinkedNode next) {
this.value = value;
this.next = next;
}
public LinkedNode(int x) {
value = x;
}
public LinkedNode getNext() {
return next;
}
public void setNext(LinkedNode next) {
this.next = next;
}
public Object getValue() {
return value;
}
}
final static int MaxLen = 9;
final static int Radix = 27;
private void Collect(String R[], LinkedNode[] head)/* 依次將各非空隊列中的記錄收集起來 */
{
int k = 0, i;
LinkedNode p;
for (i = 0; i < Radix; i++)
for (p = head[i]; p != null; p = p.next)// 遍歷桶
R[k++] = (String) p.value;// 記錄
}
private void Distribute(String[] R, LinkedNode[] head, LinkedNode[] tail, int j,
int n)/* 按關(guān)鍵字的第j個分量進(jìn)行分配，進(jìn)入此過程時各隊列一定為空 */
{
int i, k;
LinkedNode p;
for (i = 0; i < n; i++)/* 依次掃描R[i]示绊，將其入隊 */
{
if (R[i].charAt(j) == ' ')/* 空格時放入0號隊列中锭部，'a'時放入1號隊列中,... */
k = 0;
else
k = R[i].charAt(j) - 'a' + 1;
p = new LinkedNode(R[i], null);
if (head[k] == null) {
head[k] = p;// 用于存儲每一個鏈表頭的數(shù)組，將第一個加入的數(shù)據(jù)作為鏈表頭
tail[k] = p;// 用于給每一個鏈表增加數(shù)據(jù)面褐。記錄第k個鏈表上一次加入的LinkedNode拌禾。
} else {
tail[k].next = p;
tail[k] = tail[k].next;
}
}
}
private static void RadixSort(String[] R, int n) {// *對R[0...n-1]進(jìn)行基數(shù)排序*
LinkedNode[] head = new LinkedNode[Radix];
LinkedNode[] tail = new LinkedNode[Radix];
int i, j;
for (i = MaxLen - 1; i >= 0; i--) {/* 從低們到高位排序 */
for (j = 0; j < Radix; j++) {
head[j] = tail[j] = null;
}
Distribute(R, head, tail, i, n);// *第i個分量進(jìn)行分配*/
Collect(R, head);
}
}
private static void PreProcess(String[] R,
int n)/* 對單詞進(jìn)行預(yù)處理，用空格填充尾部至MaxLen長 */
{
int i, j;
for (i = 0; i < n; i++) {
if (R[i].length() < MaxLen) {
StringBuilder build = new StringBuilder(R[i]);
for (j = R[i].length(); j < MaxLen; j++)
build.append(" ");
build.append('\0');
R[i] = build.toString();
}
}
}
public static void main(String[] arg) {
String R[] = { "while", "if", "if else", "do while", "for", "case" };
int n = R.length;
System.out.printf("排序前：\n");
PreProcess(R, n);
System.out.printf("預(yù)處理后展哭；\n");
RadixSort(R, n);
System.out.printf("排序結(jié)果：\n");
EndProcess(R, n);
System.out.printf("最終結(jié)果：\n");
DispWord(R, n);
}
private static void EndProcess(String[] R, int n)/* 恢復(fù)處理湃窍，刪除預(yù)處理時填充的尾部空格 */
{
int i, j;
for (i = 0; i < n; i++) {
for (j = MaxLen - 1; R[i].charAt(j) == ' '; j--) {
StringBuilder builder = new StringBuilder(R[i]);
builder.delete(j, MaxLen - 2);
R[i] = builder.toString();
}
}
}
private static void DispWord(String R[], int n)/* 輸出單詞 */
{
int i;
System.out.printf(" ");
for (i = 0; i < n; i++)
System.out.printf("[%s]", R[i]);
System.out.printf("\n");
}
}
}
