5

下面的代码实现nfit了升序排序。

public static void main(String[] args) {
    ArrayList<Double> nfit = new ArrayList<Double>();

    nfit.add(2.0);
    nfit.add(5.0);
    nfit.add(1.0);
    nfit.add(8.0);
    nfit.add(3.0);

    // Sort individuals in ascending order
    Collections.sort(nfit);

    System.out.print(nfit);

}

输出是：

[1.0, 2.0, 3.0, 5.0, 8.0]

我的问题是如何获取已排序元素的初始索引？在这个例子中，我的问题的答案如下：

[2, 0, 4, 1, 3]

我怎样才能得到这些索引？

4

6 回答 6

4

复制 ArrayList 并排序，然后使用 indexOf。

ArrayList<Double> nfit = new ArrayList<Double>();
nfit.add(2.0);
nfit.add(5.0);
nfit.add(1.0);
nfit.add(8.0);
nfit.add(3.0);
ArrayList<Double> nstore = new ArrayList<Double>(nfit); // may need to be new ArrayList(nfit)
Collections.sort(nfit);
int[] indexes = new int[nfit.size()];
for (int n = 0; n < nfit.size(); n++){
    indexes[n] = nstore.indexOf(nfit.get(n));
}
System.out.println(Arrays.toString(indexes));

如果您想要 ArrayList 中的索引，

Collections.sort(nstore);
for (int n = 0; n < nfit.size(); n++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}
Collections.sort(nfit);

这将产生一个排序的 ArrayList nfit 和一个 ArrayList 的索引 nstore。

编辑：在for循环中

for (int n = 0; n < nfit.size(); nfit++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}

循环计数必须在 n 上迭代，而不是在 nfit 上找到更正的代码：

for (int n = 0; n < nfit.size(); n++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}
于 2013-04-03T14:29:55.480 回答
1

制作副本，ArrayList然后对副本进行排序。之后使用indexOf方法传递排序数组的元素并调用 original ArrayList。

于 2013-04-03T14:26:40.810 回答
1

如果值是唯一的，您可以使用 aMap<Double, Integer>来保存值和初始顺序。您只需要对映射键进行排序并获取每个键的对应值。

于 2013-04-03T14:27:28.237 回答
0

两种解决方案： 1）如果您与 ArrayList 结合，则需要使用 Iterator 来构建解决方案集的索引列表。2）切换到带有值和顺序的Map（可以通过排序来改变）。

于 2013-04-03T14:27:50.280 回答
0

下面的 mergesort 实现实现了一个方法 'indexSort'，它可以做到这一点而不会弄乱输入数组。 http://algs4.cs.princeton.edu/22mergesort/Merge.java.html http://algs4.cs.princeton.edu/code/javadoc/Merge.html#indexSort(java.lang.Comparable[])

于 2014-10-09T18:28:22.340 回答
0

冒泡排序永远是你的朋友。您可以使用它对数组进行排序，同时跟踪原始数组索引。当您的数组中有多个相似元素时，它也将起作用。

import java.util.*;
import java.util.Arrays;
import java.util.Random;
public class BubbleSort {
    public static void main(String[] args) {
        Random rnd = new Random();
        int count = 5;
        ArrayList<Double> array = new ArrayList<Double>();
        int[] indices = new int[count];
        for(int i = 0; i < indices.length; i++) {
            array.add(rnd.nextDouble() * count);
            indices[i] = i;
        }
        ArrayList<Double> values = new ArrayList<Double>(array);
        bubbleSort(values, indices);
        System.out.println("Unsorted input array   :" + array);
        System.out.print("Sorted   input array   : ");
        for(int i = 0; i < array.size(); i++) {
            System.out.print(array.get(indices[i]) + " " );
        }
        System.out.println();
    }
    private static void bubbleSort(ArrayList<Double> values, int[] indices) {
        for(int k = 0; k < values.size(); k++) {
            for(int l = k + 1; l < values.size(); l++) {
                if(values.get(k) > values.get(l)) {
                    double temp_value = values.get(k);
                    values.set(k, values.get(l));
                    values.set(l, temp_value);
                    int temp_index = indices[k];
                    indices[k] = indices[l];
                    indices[l] = temp_index;
                }
            }
        }
    }
}

这么多年后我回答这个问题的原因是，如果您有多个具有相似值的元素，则 接受的答案将失败，因为在indexes[n] = nstore.indexOf(nfit.get(n));，indexOf方法总是返回指定元素的第一次出现，这会导致索引数组不正确，同时具有相似的元素在输入数组中。

最后，将代码复制并粘贴进去BubbleSort.java，然后运行javac BubbleSort.java && java BubbleSort编译并查看结果。

于 2017-11-15T02:22:26.147 回答