Java 对字符串进行桶排序

Question

我想不出什么是使用桶排序对长度始终相同的字符串列表进行排序的最佳方法。

一个算法看起来像这样:

For the last character position down to the first:
    For each word in the list:
        Place the word into the appropriate bucket by current character
    For each of the 26 buckets(arraylists)
        Copy every word back to the list

我正在用 Java 编写，我正在使用一个数组列表作为存储未排序字符串的主列表。每个字符串的长度为五个字符。

这就是我的开始。它只是在第二个 for 循环中突然停止，因为我不知道下一步该做什么，或者我是否做对了第一部分。

ArrayList<String> count = new ArrayList<String>(26);

for (int i = wordlen; i > 0; i--) {
    for (int j = 0; i < myList.size(); i++)
        myList.get(j).charAt(i)
}

提前致谢。

编辑:这就是我现在拥有的。我知道这是行不通的，因为如果有多个字符串以相同的字母开头，那么它就会爆炸，但我认为我的方向更正确。当我运行它时，即使使用我放入的单词来确保没有重复的字母，它也会在第一组行上出现异常:count.set(myList.get(j).charAt(i), myList.get(j)); 显示“线程“主”java.lang.StringIndexOutOfBoundsException 中的异常:字符串索引超出范围:5”

 public void BucketSort(int wordlen) {

   ArrayList<String> count = new ArrayList<String>(26);

     //Make it so count has a size
   for(int p = 0; p < 26; p++)
       count.add(null);

    for (int i = wordlen; i > 0; i--) { //for each letter
        for (int j = 0; j < myList.size(); j++) //for each word
               //Add the word to count based on the letter
            count.add((int)myList.get(j).charAt(i) - 65, myList.get(j));
}
     //Clear the main list so there aren't a bunch of unsorted words leftover
   myList.clear();

     //Add the words back in to the list based on their order in count
   for (int m = 0; m < 26; m++)
       myList.add(count.get(m));
  }

Answer 1

这对我来说像是作业，所以我不会用代码解决方案作为回应。

但基本上，您遇到的问题是设置您的存储桶。可能你希望你的桶是 Map<Character, List<String>> -- 也就是说，您想要将每个字母 A - Z 映射到与该字母匹配的单词列表(对于您当前正在查看的位置)。该单词列表就是您的存储桶。

然后，在完成内部循环之后，您可以通过 map 的内容进行另一个循环，从 A-Z(提示:for ( char ch = 'A'; ch <= 'Z'; ch++ ))并将相应存储桶的内容转储回您的(清空)列表。