Получить индексы массива после сортировки?

Ответ 1

Не начинайте сортировку массива. Сортируйте индексный массив, передавая в компаратор, который сравнивает значения, используя их как индексы в массиве. Таким образом, вы получаете newIndex в результате сортировки, и тривиально перейти оттуда к отсортированному массиву фактических элементов.

По общему признанию, это означает сортировку массива целых чисел по-своему, что означает либо использование Integer[], либо стандартную библиотеку Java, либо стороннюю библиотеку, которая имеет интерфейс "IntComparator", который может использоваться в сочетании с sort(int[], IntComparator) тип метода.

EDIT: Хорошо, вот пример компаратора. Для простоты я предполагаю, что вы хотите только отсортировать "исходный" массив строк... и я не буду утруждать себя тестированием нечетности.

public class ArrayIndexComparator implements Comparator<Integer>
{
    private final String[] array;

    public ArrayIndexComparator(String[] array)
    {
        this.array = array;
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[array.length];
        for (int i = 0; i < array.length; i++)
        {
            indexes[i] = i; // Autoboxing
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
         // Autounbox from Integer to int to use as array indexes
        return array[index1].compareTo(array[index2]);
    }
}

Вы бы использовали его следующим образом:

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.

Ответ 2

Краткий способ достижения этого с помощью Java 8 Stream API,

final String[] strArr = {"France", "Spain", "France"};
int[] sortedIndices = IntStream.range(0, strArr.length)
                .boxed().sorted((i, j) -> strArr[i].compareTo(strArr[j]) )
                .mapToInt(ele -> ele).toArray();

Ответ 3

TreeMap<String,Int> map = new TreeMap<String,Int>();
for( int i : indexes ) {
    map.put( stringarray[i], i );
}

Теперь итератор над map.values ​​(), чтобы получить индексы в порядке сортировки, и над map.keySet(), чтобы получить строки, или над map.entrySet(), чтобы получить String-index-Pair.

Ответ 4

Я сделал следующее на основе кода @Skeet. Я думаю, что это немного больше ООПи. Я не знаю.

public static <T extends Comparable<T>> List<Integer> sortIndex(List<T> in) {
    ArrayList<Integer> index = new ArrayList<>();
    for (int i = 0; i < in.size(); i++) {
        index.add(i);
    }

    Collections.sort(index, new Comparator<Integer>() {
        @Override
        public int compare(Integer idx1, Integer idx2) {
            return in.get(idx1).compareTo(in.get(idx2));
        }
    });

    return index;
}

Вместо класса, который реализует сортировку и индексирование с кодом Comparator для разных объектов, объекты в исходном массиве должны реализовывать интерфейс Comparable. Кажется, что многие объекты, имеющие интерес, имеют естественный порядок и уже имеют интерфейс Comparable.

public static void main(String[] args) {

    List<Integer> a1 = new ArrayList<>(Arrays.asList(2, 3, 9, 4, 1));
    // Just pass in the list to have its indexes sorted by the natural ordering
    List<Integer> idx = sortIndex(a1);

    List<Double> a2 = new ArrayList<>(Arrays.asList(1.0, 5.3, 5.2, -3.1, 0.3));
    idx = sortIndex(a2);

    List<numBits> a3 = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        a3.add(new numBits(i));
    }

    // If you need to sort the indexes of your own object, you must implement
    // the Comparable Interface.
    idx = sortIndex(a3);
}

static class numBits implements Comparable<numBits> {
    private int a;

    public numBits(int i) {
        a = i;
    }

    public String toString() {
        return Integer.toString(a);
    }

    // Sort by the total number of bits in the number.
    @Override
    public int compareTo(numBits that) {
        if (Integer.bitCount(this.a) < Integer.bitCount(that.a))
            return -1;
        if (Integer.bitCount(this.a) > Integer.bitCount(that.a))
            return 1;
        return 0;
    }
}

Ответ 5

Один из способов сделать это - обернуть исходный индекс и название страны в отдельный класс. Затем отсортируйте массив по именам. Таким образом, ваши исходные индексы будут сохранены.

Ответ 6

Что приходит с первого взгляда, так это их сопоставление

Map <Integer, String> map = new HashMap<Integer, String>();
map.put(0, "France");
map.put(1, "Spain");
map.put(2, "France");

а затем отсортируйте их по значению как это, а затем вы сможете узнать их индексы и значения (ключ, значения), просто распечатайте карту

Iterator mapIterator = map.keySet().iterator();  

while (mapIterator .hasNext()) {  
     String key = mapIterator.next().toString();  
     String value = map.get(key).toString();  

     System.out.println(key + " " + value);  
}

Ответ 7

Если имеется сценарий многократной сортировки примитивных массивов float или int с положительными значениями, то метод, подобный ниже, дает намного лучшую (x3 ~ x4) скорость по сравнению с использованием любых компараторов:

long time = System.currentTimeMillis();
for (int i = 0; i < iters; i++) {           
    float[] array = RandomUtils.randomFloatArray(-1,  1, 3000);
    long[] valueKeyPairs = new long[array.length]; 
    for (int j = 0; j < array.length; ++j) {
        valueKeyPairs[j] = (((long) Float.floatToIntBits(array[j])) << 32) | (j & 0xffffffffL);
    }
    Arrays.sort(valueKeyPairs);
    /**Then use this to retrieve the original value and index*/
    //long l = valueKeyPairs[j];
    //float value = Float.intBitsToFloat((int) (l >> 32));
    //int index = (int) (l);
}
long millis = System.currentTimeMillis() - time;