按字母顺序排序数组，不使用array.在Java中排序

Question

我想对一个数组的值按字母顺序排序，使用归并排序。到目前为止，我有这段代码，但是当我运行它时，输出是混乱的，并且顺序不正确。(夏洛特敦、弗雷德里克顿、蒙特利尔、多伦多、温哥华……)

如果有人有任何建议/解决方案，我将非常感谢你的帮助:)

这是我当前的代码。

class Main {
public static void main(String[] args) {
String [] words = {
"Montreal", "Halifax", "Toronto", "Vancouver",
"Whitehorse", "Winnipeg", "Calgary", "Edmonton", 
"Hamilton", "Regina", "Saskatoon", "Sault Ste. Marie", "Moncton", "Gander", "Fredericton", "Charlottetown"};
for(int i = 0; i < words.length; i++) {
int smallest = i;
for(int j = i + 1; j < words.length; j++) {
if(words[j].compareTo(words[i]) < 0)
smallest = j;
}       
String aux = words[i];
words[i] = words[smallest];
words[smallest] = aux;
}
for(int i = 0; i < words.length; i++) {
System.out.println(words[i]);
}
}
}

Answer 1

首先，这不是归并排序，这实际上是选择排序(别担心，有这么多排序算法，很容易混淆)。

其次，你这里的问题是你只比较了word[i]的单词和每个word[j]，这不会正确排序。下面是发生的事情的一个例子:

我们有:

String[] array = "Hippo, Alligator, Bear";

:

if ( words[j].compareTo(words[i]) < 0 )

转换成

if ( Alligator.compareTo(Hippo) < 0 )

结果是:

word[smallest] = Alligator

但是它会运行:

if ( Bear.compareTo(Hippo) < 0 )

，最终结果为:

word[smallest] = Bear

因此它将Bear保存为word[smallest]，但它应该是Alligator。因此，不是比较word[i]和每个word[j]，而是比较每个word[smallest]和每个word[j]。所以你需要把words[j].compareTo(words[i])改成words[j].compareTo(words[smallest])。