如何按字典顺序对二维数组进行排序？

Question

假设我们有一个如下的二维数组：

int[][] source = {
  {   3,  5,  6,  1},
  {   3,  3,  5, -6},
  {  -1, -3, -5, -6},
  { 124, 43, 55, -66}
};

如何按字典顺序对多维数组source进行排序？

因此，我期望结果为：

[ [ -1, -3, -5,  -6], 
  [  3,  3,  5,  -6], 
  [  3,  5,  6,   1], 
  [124, 43, 55, -66] ]

这个网站上很多问题似乎只建议按每个数组的第一个、第二个、第三个等元素排序，而没有考虑整个数组。

- Ousmane D.

---

非常好的问题。我尝试以一种方式格式化示例数组，使得“字典顺序”更容易理解，通过交换以3开头的行，这样在这种情况下，下一列的值应该用于比较，这一点会更加明显。希望您不介意。 - Pshemo

Answer 1

从JDK9开始，有一个名为Arrays.compare的新方法，它允许您按字典顺序比较两个给定的数组。 Arrays.compare的简短描述来自文档：

如果两个数组共享一个公共前缀，则词典比较是比较两个元素的结果，就像通过Integer.compare(int, int)在各自数组中具有前缀长度的索引一样。否则，一个数组是另一个数组的适当前缀，并且词典比较是比较两个数组长度的结果。

如果您想要修改源数组，则使用Arrays.sort应该就足够了。

Arrays.sort(source, Arrays::compare); 

如果你想要一个新的数组作为结果，那么我会选择使用流的方式：

int[][] sorted = Arrays.stream(source)
                       .sorted(Arrays::compare)
                       .toArray(int[][]::new);

- Ousmane D.

---

在Java 8中，您可以使用Comparator.comparing(IntBuffer::wrap)作为Arrays::compare的替代品。顺便说一下，对于数组初始化器，您不需要new int[][]或new int[]。 - Holger

Answer 2

首先对数组中的每个ArrayList进行排序。

ArrayList<ArrayList<Integer>> allSubset = new ArrayList<>();

for(ArrayList<Integer> row : allSubset) {
     Collections.sort(row);
}

其次，按字典序对整个ArrayList进行排序。

allSubset.sort((ArrayList<Integer> o1, ArrayList<Integer> o2) -> {
            if(o2.size() == 0) return 1;
            int min = Math.min(o1.size(), o2.size());
            int i;
            for(i = 0; i < min - 1; i++) {
                if(o1.get(i).equals(o2.get(i))) continue;
                return o1.get(i).compareTo(o2.get(i));
            }
            return o1.get(i).compareTo(o2.get(i));
        });

或者

    Collections.sort(allSubset, (ArrayList < Integer > first, ArrayList < Integer > second) -> {
        for (int i = 0; i < first.size() && i < second.size(); i++) {
            if (first.get(i) < second.get(i))
                return -1;
            if (first.get(i) > second.get(i))
                return 1;
        }
        if (first.size() > second.size())
            return 1;
        return -1;
    });

- Sk Monjurul Haque

---

你是否尝试使用问题中的输入并将其与预期输出进行比较？ - Johannes Kuhn

是的@JohannesKuhn，对于这个问题。不要对内部数组进行排序。只需对整个数组进行排序。 System.out.println(lexicographicallySort(Arrays.asList( Arrays.asList(3, 5, 6, 1), Arrays.asList(3, 3, 5, -6), Arrays.asList(-1, -3, -5, -6), Arrays.asList(124, 43, 55, -66) )));输出：[[-1，-3，-5，-6]，[3，3，5，-6]，[3，5，6，1]，[124，43，55，-66]] - Sk Monjurul Haque

@JohannesKuhn，在上面的例子中，所有内部数组的大小都相同。但是你可以尝试使用空数组和不同大小的数组。例如：[ [], [4, 5], [12], [4, 5, 6] ] - Sk Monjurul Haque