如何对数组进行排序并跟踪java中的索引

How to sort an array and keep track of the index in java

提问by neteot

I am trying to sort (decreasing) an array of integers but keeping track of the original index.

我正在尝试对整数数组进行排序（递减），但要跟踪原始索引。

I mean, for example if I have this array:

我的意思是，例如，如果我有这个数组：

b[] = { 4, 5, 3, 5, 2 }   

after using Arrays.sort(b, Collections.reverseOrder()) it turns into ( I am using Arrays.sort, because in this example b is only length 5, but in my problem the length of b could be 1 < b.length < 70

在使用 Arrays.sort(b, Collections.reverseOrder()) 之后它变成了（我使用的是 Arrays.sort，因为在这个例子中 b 的长度只有 5，但在我的问题中 b 的长度可能是 1 < b.length < 70

b[] = { 5, 5, 4, 3, 2 }

but I want to somehow have the original index, I mean knowing that

但我想以某种方式拥有原始索引，我的意思是知道

bOrignalIndex[] = { 1, 3, 0, 2, 4 }

I don't know if my question in clear, please ask me everything. I have this piece of code in C++ that can be helpful because it does what I want

我不知道我的问题是否清楚，请问我一切。我在 C++ 中有这段代码，它可能会有所帮助，因为它可以满足我的需求

n=4
m=5
tord[] =  
[0] 0   
[1] 1   
[2] 2   
[3] 3   
ts[] =      
[0] 4   
[1] 5   
[2] 3   
[3] 5   



   tord[MAXT], ts[MAXT];
       bool ord(int a, int b){
        return ts[a] > ts[b];    }
    int main(void){
        for(int m, n; scanf("%d %d", &m, &n)){
            bool possible = true;
            FOR(i=0;i<m, i++){ // for each team
                scanf("%d", ts + i); // read team size
                tord[i] = i;
            }
            sort(tord, tord + m, ord)

The thing is after doing this, tord has the array ordered by index, that is:

事情是这样做之后， tord 具有按索引排序的数组，即：

tord[] =  
[0] 1   
[1] 3   
[2] 0   
[3] 2   

采纳答案by Alexey Malev

Try sorting pairs of (value, index)compared by value:

尝试(value, index)按值对比较的对进行排序：

public class Pair implements Comparable<Pair> {
    public final int index;
    public final int value;

    public Pair(int index, int value) {
        this.index = index;
        this.value = value;
    }

    @Override
    public int compareTo(Pair other) {
        //multiplied to -1 as the author need descending sort order
        return -1 * Integer.valueOf(this.value).compareTo(other.value);
    }
}

Then, when you're going to sort:

然后，当你要排序时：

public static void main(String[] args) {
    Pair[] yourArray = new Pair[10];

    //fill the array
    yourArray[0] = new Pair(0, 5); yourArray[1] = new Pair(1, 10); //and so on
    Arrays.sort(yourArray);
}

Now, you have an array of Pairobject ordered by valuedescending. Each object also contains index- the place in the original array.

现在，您有一个Pair按value降序排列的对象数组。每个对象还包含index- 在原始数组中的位置。

P. S. I wrote the sample in Java as the question has javatag. Although, in C++the idea is the same, only the implementation is a little bit different.

PS我用Java编写了示例，因为问题有java标签。虽然，在C++思想上是一样的，只是实现上有点不同。

回答by user3624334

The OP poster's example involved sorting an array of integer. If any of the readers have a similar situation, but with an array of non-primitive types, the following is a class that handles this for arrays of non-primitives. The class takes a somewhat different approach. It leaves the original array unmodified but instead creates an array of indexes and sorts and returns that.

OP 海报的示例涉及对整数数组进行排序。如果任何读者有类似的情况，但使用非原始类型的数组，以下是处理非原始数组的类。该类采用了稍微不同的方法。它不修改原始数组，而是创建一个索引数组，然后排序并返回它。

public class IndirectSorter<T extends Comparable<T>> {
    public int[] sort(T args[]) {
        Integer origindex[] = new Integer[args.length];
        int retval[] = new int[args.length];
        for (int i=0; i<origindex.length; i++) {
            origindex[i] = new Integer(i);
        }
        Arrays.sort(origindex, new IndirectCompareClass<T>(args));
        for (int i=0; i<origindex.length; i++) retval[i] = origindex[i].intValue();
        return retval;
    }

    class IndirectCompareClass<T extends Comparable<T>> implements Comparator<Integer> {
        T args[];
        public IndirectCompareClass(T args[]) { this.args = args; }
        public int compare( Integer in1, Integer in2 ) {
            return args[in1.intValue()].compareTo(args[in2.intValue()]);
        }
        public boolean equals( Integer in1, Integer in2 ) {
            return args[in1.intValue()].equals(args[in2.intValue()]);
        }
    }
}

And to call it quickly you can do something like this:

要快速调用它，您可以执行以下操作：

public static void main(String args[] ) {
    int indexes[] = new IndirectSorter<String>().sort(args);
    for (int i : indexes) {
        System.out.printf("original pos: %d %s\n", i, args[i] );
    }
}

Edit: If you're willing to reimplement the Arrays.sort(int[]) method, you can avoid the creation and use of Integer objects. This can be appealing.

编辑：如果您愿意重新实现 Arrays.sort(int[]) 方法，则可以避免创建和使用 Integer 对象。这可能很有吸引力。

回答by Salman

The following answer provides the main steps to overcome the issue explained in the question without details code provided.

以下答案提供了解决问题中解释的问题的主要步骤，但未提供详细代码。

• you can create custom Classthat has two attributes valueand index. where valueis the original attribute value and indexis the position before sorting.
• create an ArrayListof this Class.
• add the new objects of the created Classwith the wanted valueand index.

• 您可以创建Class具有两个属性value和index. 其中value是原始属性值，index是排序前的位置。
• 创建一个ArrayListthis Class。
• 添加Class使用想要的value和创建的新对象index。

Note:one possible way to set the indexvalue is to iterate through the Arraylistand set the value of indexusing loop index.

注意：设置index值的一种可能方法是迭代Arraylist并设置indexusing 循环索引的值。

• sort the Arraylistusing specialComparablebased on valueattribute.

• 根据属性对Arraylistusing special 进行排序。Comparablevalue

now after sorting you can know the previousindexof any entry by invoking its indexattribute.

现在排序后，您可以index通过调用其index属性来了解任何条目的前一个。