看见过c++，c#解此题，未见java，寄己写一篇，加深印象。
算法题之前理清思路。关键点： 基数排序
-
准备工作：
1 :根据最大长度（MaxLen）把单词都最后补位成空格填充尾部至MaxLen长的单词。比如“abdd”“abd”。则“abdd”“abd ”。
2:弄27个桶，第一个桶对应“ ”，另外26个桶对应26个字母；
3:每个桶用队列的形式存储。(用LinkedNode需准备两个LinkedNode[] 一个存头，一个用于往链表加元素)
-
排序：
按关键字的第j（从MaxLen-1到0）个分量进行分配（进入此过程时各队列一定为空），依次将各非空队列中的记录收集起来，循环到第0个分量
-
结束工作：
恢复处理，删除预处理时填充的尾部空格。
输出。
-
代码
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)/* 按关键字的第j个分量进行分配，进入此过程时各队列一定为空 */
{
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;// 用于存储每一个链表头的数组，将第一个加入的数据作为链表头
tail[k] = p;// 用于给每一个链表增加数据。记录第k个链表上一次加入的LinkedNode。
} else {
tail[k].next = p;
tail[k] = tail[k].next;
}
}
}
private static void RadixSort(String[] R, int n) {// *对R[0...n-1]进行基数排序*
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个分量进行分配*/
Collect(R, head);
}
}
private static void PreProcess(String[] R,
int n)/* 对单词进行预处理，用空格填充尾部至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("预处理后；\n");
RadixSort(R, n);
System.out.printf("排序结果：\n");
EndProcess(R, n);
System.out.printf("最终结果：\n");
DispWord(R, n);
}
private static void EndProcess(String[] R, int n)/* 恢复处理，删除预处理时填充的尾部空格 */
{
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");
}
}
}
