字符串基数排序 - StringIndexOutOfBoundsException

Question

我正在编写自己的基数排序方法，用于对字符串中的单词进行排序（例如“the big black cat sat on the beautiful brown mat”将按照“beautiful big black brown cat mat on sat the the”的顺序排序）。该方法接受一个列表（我的自定义列表接口）作为参数，并直接在原地重新排列该列表。

以下是我目前的方法：

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()” - 就会抛出异常，因此它试图使用大于字符串长度的String索引创建子字符串。

我应该如何调整我的方法，使其仅在“letterNumber == word.length()”之前创建每个单词的子字符串，并能将排序算法应用于这些较短的单词 - “a”将变成“aa”的前面。

- KOB

---

在列表中似乎有一个空单词。这可能是因为在非单词字符上分割时它们位于开头或结尾，或者没有考虑到单词之间可能有多个非单词字符。 - Joop Eggen

Answer 1

将长度小于字符串长度的元素分组到一个额外的组中。此外，您需要首先按最不重要（相关）的字符进行排序。以下代码使用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();
            }
        }
    }
}

- fabian

---

我喜欢这个解决方案，其中buckets [0]保存较短的单词。如果buckets [0]中的列表包含多个单词，它们仍然会被排序吗？抱歉，我现在没有时间完全分析您的解决方案，但稍后我会告诉您我的进展情况。 - KOB

@KOB：是的。如果您使用 ('a'-1) 填充 String，则会产生与此相同的顺序。因此，如果它们具有相同的前缀，则仅优先选择较短的字符串而不是较长的字符串...请注意，该算法从最低有效位字符开始，并利用桶中的元素保持在列表之前的相同顺序的事实。在循环的每次迭代之后，列表将按以索引 i 开始的子字符串排序，其中将空字符串视为太大的索引的子字符串。 - fabian

很不幸，我的代码使用了我自己的List接口，所以我不能更改这个类来使用Java Utils List。我已经编辑了你的解决方案，使用了我的List - 据我所知，它并没有改变算法的功能，只是更改了用于编辑List的List方法。这是我的编辑版本。这将10: the big black cat sat on the beautiful brown mat排序为8: cat beautiful big the mat on sat the，其中10和8是每个列表的大小，在我的toString方法中添加。 - KOB

Answer 2

为什么不替换？

String letter = word.substring(letterNumber - 1, letterNumber);
char ch = letter.charAt(0);

使用

char ch = word.charAt(letterNumber - 1);

这可以直接给你一个char。但这并不能解决IndexOutOfBoundException的问题。

当然，您应该捕获异常并处理它。也许为这种情况创建一个桶是个好主意：当单词对于当前迭代太短时，将其分类到一个桶中。在合并列表时，首先取出这个桶中的元素。

public static void stringRadixSort(List<String> list, int letters) {
    List<String>[] buckets = (List<String>[]) Array.newInstance(List.class, 27);

    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);
            int index;
            if(word.length() > letterNumber) {
                char ch = word.charAt(letterNumber - 1);
                index = ch - 'a' + 1;    //gets index of each letter ('a' = buckets[1], 'z' = buckets[26], buckets[0] is for short words
            } else {
                index = 0;
            }
            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++;
    }
}

- l7r7

---

是的，我明白了。我会尝试查看这个问题。 - l7r7

使用 try/catch 而不是 if 是一种不好的做法。由于测试某个给定 String 的特定索引是否会抛出 IndexOutOfBoundsException 很容易，因此应该使用 if 而不是 try/catch。 - fabian

@user187470 我喜欢那个解决方案，但我现在无法访问我的代码，所以我稍后会实现它并告诉你它的效果如何。谢谢。 - KOB

@fabian 我更新了我的回答，谢谢。这样好多了。 - l7r7

这也是我在测试时对你的解决方案所做的更改，但不幸的是排序是不正确的。我尝试的排序方式是按照第一个字母、第二个字母等进行排序，而不管每个单词中有多少个字母。例如，单词 bb, b, bc, c, abcd, bcd 将按照 abcd, b, bb, bc, bcd, c 进行排序。因此句子 the big black cat sat on the beautiful brown mat 将被排序为 beautiful big black brown cat mat on sat the the。而你的算法则是按照单词长度和字典顺序进行排序，结果为 on cat mat sat the the big black brown beautiful。 - KOB

Answer 3

在尝试的过程中，我一直在按最重要的字母（每个单词的第一个字母）排序，然后按下一个最重要的字母进行排序，以此类推。当然，基数排序依赖于对数字/单词的最不重要的数字/字母（即数字/单词的最后一个数字/字母）进行排序。因此，我改变了我的外部for循环迭代的方式，从letterNumber = 1开始关注并在每次迭代后递增，转而使用letterNumber = maxWordLength开始，并在每次迭代后递减，以便每次迭代都比较下一个最重要的字母。

@SuppressWarnings("unchecked")
public static void stringRadixSort(List<String> list) {
    List<String>[] buckets = (List<String>[]) Array.newInstance(List.class, 27);

    //Find longest word in list
    int maxWordLength = 0;
    for (String word : list) {
        if (word.length() > maxWordLength) {
            maxWordLength = word.length();
        }
    }

    //Sorts list based on least significant letter (last letter of word) to most significant
    int letterNumber = maxWordLength;
    for (int i = 0; i < maxWordLength; i++) {
        while (!list.isEmpty()) {
            String word = list.remove(list.first());
            int index = 0;
            if(word.length() >= letterNumber) {
                char ch = word.charAt(letterNumber - 1);
                index = ch - 'a' + 1;    //gets index of each letter ('a' = buckets[1], 'z' = buckets[26], buckets[0] is for words shorter than 'letterNumber')
            }
            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--;
    }
}

- KOB