低效的存储桶排序？

Question

我正在尝试使用桶排序算法对字符串进行排序。这个任务说运行时间应该是0.05秒，但我的运行时间超过9秒。为什么我的运行时间这么长，我怎么才能让它更快。它在文件中有大约90000个名字。我是否正确地进行了存储桶排序？

public static void bucketSortByLength() {
      String[] bucket = new String[14];
      String[] insideBucket;
      int index = 0;
      for(int i = 0; i <= 13; i++)
        bucket[i] = "";
      for(int i = 0; i < numNames; i++)
        bucket[names[i].length()] += names[i] + " ";
      for(int i = 0; i <= 13; i++){
        insideBucket = bucket[i].split("\\s+");
        for(String s : insideBucket)
          names[index++] = s;
      }
    }

Answer 1

您的代码很可能很慢，因为它所做的事情在Java语言中可能非常低效：String值是不可变的，因此每次连接都会创建一个完整的新字符串。

您应该使用支持存储桶有效追加的数据类型。出现在脑海中的两个选项是StringBuilder和LinkedList<String>。(当我最后一次每天使用Java时，后者可能会更好，现在可能仍然如此。)

Answer 2

正如其他人所说，由于字符串连接，这是低效的。

一个很好的经验法则：

当你在一个循环中发现自己连接的字符串时，最好使用一个 StringBuilder**.**

请参阅：When to use StringBuilder in Java

这段代码应该会提供您所期望的性能：

public static void bucketSortByLength() {
    StringBuilder[] bucket = new StringBuilder[14];
    int index = 0;
    for(int i = 0; i <= 13; i++)
        bucket[i] = new StringBuilder();
    for(int i = 0; i < numNames; i++)
        bucket[names[i].length()].append(names[i]).append(' ');

    for(int i = 0; i <= 13; i++){
        String[] insideBucket = bucket[i].toString().split("\\s+");
        for(String s : insideBucket)
            names[index++] = s;
    }
}