java - 如何按升序对段数组 (int left, int right) 进行排序，但如果 left(i)=left(i+1) 则根据 right(i) 和 right(i+1) 对其进行排序

Question

我有一个 Segment 类和一个这样的段数组:

private static class Segment {
        int number, type;
        Segment(int number, int type) {
            this.number = number;
            this.type = type;
        }
}

Segment[] points = new Segment[n];
points={(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)}

左边的元素是一个点的列表，右边的列表是点的类型:-1打开一个线段，1关闭一个线段，0与线段相交。正如您所看到的，这个数组已经根据数字排序，使用这个代码(它是一个改编的 selectionSort):

maxI 找到最大“数”元素的索引

private static int maxI(Segment[] segments, int size){
    int max=0;
    for (int i=0; i< size;i++){
        if(segments[i].number > segments[max].number ){
             max=i;
        }   
    }
    return max;
}

//swap 方法在 index1 和 index2 之间交换数组的元素

private static void swap(Segment[] segments, int index1, int index2){
            int temp1; 
            int temp2;
            temp1 = segments[index1].number;
            temp2 = segments[index1].type;
            segments[index1].number=segments[index2].number;
            segments[index1].type=segments[index2].type;
            segments[index2].number=temp1;
            segments[index2].type=temp2;
    }

selectSort 是排序方法(因为 Arrays.sort 不适用于“段”)

private static void selectSort(Segment[] segments) {
        int MaxPos;
        for (int i=segments.length-1;i>0;i--){
            MaxPos = maxI(segments, i+1);
            swap (segments, MaxPos, i);
        }
}

原始输入是 2 个范围和 3 个交点:

Range 1: 0 5
Range 2: 6 10
Intersection points: 1 6 11

所以排序后的结果如上:

(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)

我已经尝试修改 maxI 方法，所以 6,-1 使用第二个 if 语句出现在 6,0 (-1 < 0) 之前:

if (segments[i].number = segments[max].number && segments[i].type > segments[max].type)

但它会弄乱输出。由于输入是随机的，因此必须准备代码来对许多数字相等的测试用例进行排序。

我见过的与此主题最接近的问题是 one made in C++ ，我只是在学习 Java，所以我很努力地尝试理解 C++。我觉得答案很接近，但不确定我错过了什么。也许我使用了错误的数据结构。在这之后我只是遍历数组，添加类型的总和，所以如果一个数字通过 3 个范围的开放(x，-1)，它是 -3，在 absolute= 3 所以它与 3 个范围相交，这就是我的答案会需要的。

Answer 1

只需创建一个Comparator 来比较number，然后比较type，然后您就可以使用Arrays.sort() .如果你有 Java 8，你可以这样做:

Arrays.sort(points, Comparator.comparingInt((Segment s) -> s.number).thenComparingInt((Segment s) -> s.type));

如果您使用的是 Java 7，您可以这样做:

Arrays.sort(points, new Comparator<Segment>() {
    @Override
    public int compare(Segment s1, Segment s2) {
        int result = Integer.compare(s1.number, s2.number);
        if (result == 0) {
            result = Integer.compare(s1.type, s2.type);
        }
        return result;
    }
});

或者，您可以让 Segment 实现 Comparable 接口(interface)，Arrays.sort(points) 将开箱即用:

private static class Segment implements Comparable<Segment> {
    int number, type;
    Segment(int number, int type) {
        this.number = number;
        this.type = type;
    }

    @Override
    public int compareTo(Segment s) {
        int result = Integer.compare(this.number, s.number);
        if (result == 0) {
            result = Integer.compare(this.type, s.type);
        }
        return result;
    }
}