Java 实现 单词排序———基数排序

看见过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");
    }
}
}