使用基数排序实现英文单词字母表顺序排序，时间复杂度 O(n)

1、题目

英文单词由 26 个字母组成，现要求设计一个算法，对一组乱序单词实现字母表顺序排序。java

2、思路和分析

算法的选择有不少，这里咱们选择使用 基数排序，这是一种时间复杂度为 O(n) 的排序算法，关于它的介绍，也能够参考个人这一篇博文：http://www.noobyard.com/article/p-dkvobxhi-tb.html算法

不考虑大小写的话，咱们须要准备 26 个桶来存放不一样的 26 个字母，其次，咱们还须要一个额外的桶来存放那些空字符的状况。咱们把空字符放在第零个桶内，其次 a~z 个字母依次放在第一到第二十六个桶内。ui

3、代码

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        String[] words = new String[] { "select", "bubble", "quick", "insert", "merge",
                "heap", "count", "bucket", "radix" };
        radixSort(words);
        printArray(words);
    }

    public static void radixSort(String[] arr) {
        int length = getMaxLength(arr); // 获取最长的单词长度
        for (int i = length - 1; i >= 0; i--) {
            bucketSort(arr, i); // 执行 length 次 bucketSort 排序便可
        }
    }

    public static int getMaxLength(String[] words) {
        int length = 0;
        for (String word : words) {
            if (word.length() > length) {
                length = word.length();
            }
        }
        return length;
    }

    public static void bucketSort(String[] words, int charIndex) {
        // init buckets
        ArrayList<ArrayList<String>> buckets = new ArrayList<ArrayList<String>>();
        for (int i = 0; i < 27; i++) {
            buckets.add(new ArrayList<String>());
        }
        // sort
        for (String word : words) {
            buckets.get(getBucketIndex(word, charIndex)).add(word);
        }
        // output: copy back to arr
        int index = 0;
        for (ArrayList<String> bucket : buckets) {
            for (String word : bucket) {
                words[index++] = word;
            }
        }
    }

    public static int getBucketIndex(String word, int charIndex) {
        if (charIndex >= word.length()) {
            return 0; // 第 0 个桶存非字母状况
        }
        int index = 0;
        char c = word.charAt(charIndex);
        if (64 < c && c < 91) { // 大写字母
            index = c - 64;
        } else if (96 < c && c < 123) { // 小写字母
            index = c - 96;
        } else { // 其他非字母字符
            index = 0;
        }
        return index;
    }

    public static void printArray(String[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

执行结果：.net

bubble bucket count heap insert merge quick radix select 设计

4、继续思考

对于绝大多数状况下上述代码均可以比较快的运行。可是，当某个单词特别长的时候，致使 length 变得很大，循环次数就变得很大了，这是咱们不但愿看到的。code

其实，很长的单词可能并非不少，咱们能够挑出这少部分的超长单词，单独对待。最后使用插入排序或者合并排序的方式将这少部分的超长单词加入进去。blog

​