我正在编写自己的基数排序方法来对字符串中的单词进行排序(大黑猫坐在
beautiful brown mat
将被分类为 beautiful big black brown cat mat on sat the the
)。该方法接收单个单词的 List(我自己的 List 接口(interface))并重新排列列表。
到目前为止,这是我的方法:
public static void stringRadixSort(List<String> list, int letters) {
List<String>[] buckets = (List<String>[]) Array.newInstance(List.class, 26);
int letterNumber = 1; //Sorts list by 1st letter of each word, then 2nd etc.
for (int i = 0; i < letters; i++) {
while (!list.isEmpty()) {
String word = list.remove(list.first());
if (word.length() > letters) throw new UnsortableException("The list contains a word that holds more letters than the given maximum number of letters."
+ "\nMax Letters: " + letters + "\nWord: " + word);
String letter = word.substring(letterNumber - 1, letterNumber); //EXCEPTION THROWN
char ch = letter.charAt(0);
int index = ch - 'a'; //gets index of each letter ('a' = buckets[0], 'z' = buckets[25]
if (buckets[index] == null) {
buckets[index] = new LinkedList<String>();
}
buckets[index].insertLast(word);
}
for (int j = 0; j < buckets.length; j++) {
if (buckets[j] != null) {
while (!buckets[j].isEmpty()) {
list.insertLast(buckets[j].remove(buckets[j].first()));
}
}
}
letterNumber++;
}
}
我的方法的(唯一的,我希望的)问题是,当我读取单词的每个字符时,我创建了单词的单个字母子字符串。由于外部 for
循环运行了 letters
次(其中 letters
是 List 中单词的最大长度),当此循环的迭代次数大于当前单词的长度 - 即 letterNumber > word.length()
- 因此它尝试使用大于字符串长度的字符串索引创建子字符串.
如何调整我的方法,使其只创建每个单词的子字符串,直到 letterNumber == word.length()
,然后才能将排序算法应用于这些较短的单词 - “a”将成为“aa”之前。
最佳答案
只需将比字符串长度短的元素分组到一个额外的组中。您还需要先对最不重要(相关)的字符进行排序。以下代码使用 java 集合而不是您使用的任何数据结构:
public static void stringRadixSort(List<String> list, int letters) {
if (list.size() <= 1) {
return;
}
List<String>[] buckets = new List[27];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new LinkedList<>();
}
int largestLength = -1;
int secondLargestLength = 0;
for (String s : list) {
int length = s.length();
if (length >= largestLength) {
secondLargestLength = largestLength;
largestLength = length;
} else if (secondLargestLength < length) {
secondLargestLength = length;
}
}
if (largestLength > letters) {
throw new IllegalArgumentException("one of the strings is too long");
}
for (int i = secondLargestLength == largestLength ? secondLargestLength-1 : secondLargestLength; i >= 0; i--) {
for (String word : list) {
int index = (word.length() <= i) ? 0 : word.charAt(i) - ('a' - 1);
buckets[index].add(word);
}
list.clear();
for (List<String> lst : buckets) {
if (lst != null) {
list.addAll(lst);
lst.clear();
}
}
}
}
关于java - 字符串基数排序 - StringIndexOutOfBoundsEception,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36476183/