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

Question

например, у меня есть этот массив

int[] a = {6,10,16,11,7,12,3,9,8,5};

я хочу отсортировать его индексы следующим образом

[6,9,0,4,8,7,1,3,5,2]

, чтобы я мог использовать индексы для сортировки от наименьшего к наибольшему значению,в моем коде я получил вместо этого

[6, 9, 4, 8, 7, 4, 5, 6, 6, 6] 

это мой код

int[] a = {6,10,16,11,7,12,3,9,8,5};
int[] indeks = indekssortering(a);
System.out.println(Arrays.toString(indeks));

public static int[] indekssortering(int[] a){
    int[] indeks = new int[a.length];
    int m = 0;
    boolean finnes = false;
    boolean nyVerdi = false;
    int n = 0;
    for (int j = 0; j < a.length; j++) {
        for (int i = m+1; i < a.length ; i++) {
            if(a[m] > a[i]){
                for (int k = 0; k < j; k++) {
                    if(indeks[k] == i) finnes = true; //check if the same position is saved before
                }
                if(!finnes){ // if not so its the next minimum value
                    m = i;
                } else {
                    nyVerdi = true; // if didnt find match then the value used to compare is the next minimum
                }
            }
            finnes = false;
        }
        indeks[j] = m;
        if(nyVerdi) n=n+1;
        nyVerdi = false;
        m=0+n;
    }
    return indeks;
}

Мне нужна помощь, чтобы заставить этот код работать или найти лучшую идею, чем эта.

я пытался это сделать.сравните все значения с первыми значениями, получите наименьшее и сохраните позицию в массиве (индекс).перед сохранением я сделал цикл, чтобы проверить, была ли эта позиция добавлена ​​ранее.и если нет значения, превышающего значение, используемое для сравнения, это означает следующее небольшое значение.некоторые из них я понял правильно, а другие неправильно.Я считаю, что мне нужно изменить эту идею и найти лучшее решение.

Answer 1

С java 8 вы можете использовать лямбда-сравнение.При желании вы можете затем изменить порядок [] и I [] на месте в соответствии с I [].

package x;
import java.util.Arrays;
public class x {
    // although I[] needs to be of type Integer, a[] doesn't
    public static void main(String[] args) {
        int[] a = {6,10,16,11,7,12,3,9,8,5};
        // generate array of indices
        Integer[] I = new Integer [a.length];
        for(int i = 0; i < I.length; i++)
            I[i] = i;
        // sort I[] according to a[]
        Arrays.sort(I, (i, j) -> a[i]-a[j]);
        // display result
        for (int i = 0; i < a.length; i++)
            System.out.println(a[I[i]]);

        // optional inplace reorder a[] and I[] according to I[]
        // time complexity is O(n)
        for(int i = 0; i < I.length; i++){
            if(i != I[i]){
                int t = a[i];
                int j;
                int k = i;
                while(i != (j = I[k])){
                    a[k] = a[j];
                    I[k] = k;
                    k = j;
                }
                a[k] = t;
                I[k] = k;
            }
        }
        // display result
        System.out.println();
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}

Answer 2

По сути, вы ищете перестановку массива.В частности, для перестановки сортировки.

К сожалению, обозначения несколько двусмысленны и запутаны при обращении к индексам.Основное различие заключается в том, должен ли

sorted[indices[i]] = array[i]

или

sorted[i] = array[indices[i]]

давать отсортированный массив.По вашему вопросу вы ищете последнее.

Это может быть реализовано различными способами, либо путем помещения элементов в List<Integer> и сортировки этого списка с использованием компаратора, который ссылается на исходный массив, либо путем сортировки списка «пар», каждая из которых состоит изстоимости и ее исходного индекса.(Этот подход был в основном уже показан tdelev в его ответе )

Вот реализация, которая явно вычисляет индексный массив и применяет его как перестановку к входному массиву:

import java.util.Arrays;
import java.util.Comparator;
import java.util.function.IntBinaryOperator;

public class SortingPermutations
{
    public static void main(String[] args)
    {
        int[] a = {6,10,16,11,7,12,3,9,8,5} ;
        int[] p = computeAscendingSortingPermutation(a);
        int[] s = applyPermutation(a, p);

        System.out.println("array       : " + Arrays.toString(a));
        System.out.println("permutation : " + Arrays.toString(p));
        System.out.println("sorted      : " + Arrays.toString(s));
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted in ascending order.
     * 
     * @param array The array
     * @return The sorting permutation
     */
    private static int[] computeAscendingSortingPermutation(int array[])
    {
        return computeSortingPermutation(array, Integer::compare);
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted according to
     * the given comparator
     * 
     * @param array The array
     * @param intComparator The comparator for the integer values
     * @return The sorting permutation
     */
    private static int[] computeSortingPermutation(
        int array[], IntBinaryOperator intComparator)
    {
        class Entry
        {
            int value;
            int index;
        }
        int n = array.length;
        Entry entries[] = new Entry[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = new Entry();
            e.value = array[i];
            e.index = i;
            entries[i] = e;
        }
        Comparator<Entry> comparator = 
            (e0, e1) -> intComparator.applyAsInt(e0.value, e1.value);
        Arrays.sort(entries, comparator);
        int result[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = entries[i];
            result[i] = e.index;
        }
        return result;
    }


    /**
     * Apply the given permutation to the given array, and return the result
     * as a new array. The result will be an array <code>r</code> where
     * <code>r[i] = array[permutation[i]]</code>
     * 
     * @param array The input array
     * @param permutation The permutation
     * @return The result array
     */
    private static int[] applyPermutation(int array[], int permutation[])
    {
        int n = array.length;
        int result[] = new int[n];
        for (int i=0; i<n; i++) 
        {
            result[i] = array[permutation[i]];
        }
        return result;
    }

}

Выход

array       : [6, 10, 16, 11, 7, 12, 3, 9, 8, 5]
permutation : [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
sorted      : [3, 5, 6, 7, 8, 9, 10, 11, 12, 16]

, как и ожидалось.

Answer 3

• Используйте Map.Пусть key будет элементом, а value будет queue из indices, при котором это произошло для этого значения.

• Сортировка массива.Теперь опросите каждый элемент из его очереди, хранящейся на карте.

• Сложность времени: O (n * log (n))

• Сложность пространства:O (n)

Код:

import java.util.*;
public class Solution {
    public static void main(String[] args){
        int[] a = new int[]{6,10,16,11,7,12,3,9,8,5};
        int[] result = new int[a.length];
        Map<Integer,Queue<Integer>> map = new HashMap<>();
        for(int i=0;i<a.length;++i){
            if(map.containsKey(a[i])){
                map.get(a[i]).offer(i);
            }else{
                Queue<Integer> q = new LinkedList<Integer>();
                q.offer(i);
                map.put(a[i],q);
            }
        }

        Arrays.sort(a);
        for(int i=0;i<result.length;++i){
            result[i] = map.get(a[i]).poll();
        }

        System.out.println(Arrays.toString(result));
    }
}

ВЫХОД:

[6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Answer 4

Если доступна библиотека для indexOf(int[], int) (например, Guava), вы можете получить ее очень легко:

int[] a = { 6, 10, 16, 11, 7, 12, 3, 9, 8, 5 };
int[] b = Arrays.copyOf(a, a.length);
Arrays.sort(b);
Arrays.setAll(b, i -> indexOf(a, b[i])); // b = [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Если библиотека недоступна, вот реализация indexOf(int[], int):

public static int indexOf(int[] array, int search) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == search) {
            return i;
        }
    }
    return -1;
}

Answer 5

Здесь классический алгоритм пузырьковой сортировки , модифицированный для сортировки индексов

Что вы ищете, так это любой алгоритм сортировки, который сортирует int [] array. Это бесконечный список реализаций по всему Интернету. А затем просто измените сравнение на array[result[i]] и измените значения в result, а не в array itseft.

static int[] sort(int[] array) {
    final int size = array.length;

    final int[] result = new int[size];
    for (int i = 0; i < size; i++)
        result[i] = i;

    boolean sorted;
    do {
        sorted = true;
        int bubble = result[0];
        for (int i = 0; i < size - 1; i++) {
            if (array[bubble] > array[result[i + 1]]) {
                result[i] = result[i + 1];
                result[i + 1] = bubble;
                sorted = false;
            } else {
                bubble = result[i + 1];
            }
        }
    } while (!sorted);

    return result;
}

result arrays for your input data is [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Answer 6

Вот решения без и с Java 8 Stream API.

import java.util.*;
import java.util.stream.IntStream;

public class SortIndices {

    static class Indexed {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }
    }

    static int[] indexesSorted(int[] input) {
        // Without using Stream API
        List<Indexed> indexed = new ArrayList<>();
        for(int i = 0; i < input.length; ++i) {
            indexed.add(new Indexed(input[i], i));
        }
        Collections.sort(indexed, Comparator.comparing(it -> it.number));
        int[] result = new int[indexed.size()];
        for(int i = 0; i < input.length; ++i) {
            result[i] = indexed.get(i).index;
        }
        return result;
        // Using Stream API
        /*return IntStream.range(0, input.length)
                .mapToObj(i -> new Indexed(input[i], i))
                .sorted(Comparator.comparing(it -> it.number))
                .mapToInt(it -> it.index)
                .toArray();*/
    }

    public static void main(String[] args) {
        int[] result = indexesSorted(new int[]{6, 10, 16, 11, 7, 12, 3, 9, 8, 5});
        System.out.println(Arrays.toString(result));
    }
}

Если вы не можете использовать Java 8, можно использовать интерфейс Comparable на Indexed

    static class Indexed implements Comparable<Indexed> {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }

        @Override
        public int compareTo(Indexed o) {
            return Integer.compare(number, o.number);
        }
    }

и затем вызовите Collections.sort без второго аргумента.