按字母顺序对数组进行排序

Question

我有一个数组，需要按出现次数和字母顺序排序其元素。

例如：

55 The
32 ASomething
32 BSomething

ASomething should come before Bsomething because:
1) they have the same number
2) A comes before B alphabetically

所以，首先按出现次数排序，然后按字母顺序排序。

那么，最好的方法是什么呢？我正在使用归并排序来对计数进行排序，但是如何编写语句来检查它们是否具有相同的数字，并按字母顺序排序（可能超过2个单词）。

解决方案：在对数据的计数进行归并排序之前，我对数据进行了归并排序，这已经足够好了 :) 感谢大家的帮助。

- user220755

---

这并不影响您处理计数的方式，但您的排序是区分大小写还是不区分大小写？ - shoover

我第一个想法是，哇，这在Bash shell中真的很容易。 :) - shoover

是的，我看到你在使用Java。这就是为什么有笑脸的原因。我可以用Java做到这一点，但需要比一个管道bash命令的1行更多的工作。 :D - shoover

Answer 1

你需要使用Arrays.sort()并编写一个自定义的Comparator来实现该功能：

Arrays.sort(array, new CustomComparator());

public class CustomComparator implements Comparator<String> {
  private final Pattern pattern = Pattern.compile("(\\d+)\\s+(.*)");

  public int compare(String s1, String s2) {
    Matcher m1 = pattern.matcher(s1);
    if (!m1.matches()) {
      throw new IllegalArgumentException("s1 doesn't match: " + s1);
    }
    Matcher m2 = pattern.matcher(s2);
    if (!m2.matches()) {
      throw new IllegalArgumentException("s2 doesn't match: " + s2);
    }
    int i1 = Integer.parseInt(m1.group(1));
    int i2 = Integer.parseInt(m2.group(1));
    if (i1 < i2) {
      return 1;
    } else if (i1 > i2) {
      return -1;
    }
    return m1.group(2).compareTo(m2.group(2));
  }
}

对于Collections，您可以使用Collections.sort()。

以上假设您的数组元素是像"22 ASomething"这样的String，而不是包含出现次数和一些文本的特定数据结构。如果是这种情况，您可以使用更简单的Comparator。

此外，如果您确实有一个String数组，那么首先将其转换为已解析的对象数组可能会更值得，以节省过度解析元素（即某些元素将被解析多次）。

- cletus

Answer 2

在使用 java.util.Collections.sort 时，您应确保所使用的排序算法保证了“稳定性”：

这种排序保证是稳定的：相等的元素不会因排序而重新排列。

您没有提及正在使用哪种数据结构，这肯定会指导您的方法。例如，您可以使用一个Map>来模拟您的数据，这样按顺序对List进行排序，然后迭代Map的有序键就很有意义。这不需要自定义比较器。

- msw

---

你认为为什么OP需要一个“稳定”的排序算法？ - Grzegorz Oledzki

因为 OP 执行了二次排序，“所以首先按出现次数排序，然后按字母顺序排序”。 - msw