Сортируйте целые числа, но сохраняйте индексы, чтобы восстановить их порядок

Question

Я хочу, чтобы вы предложили способ, которым я хочу отсортировать набор целочисленных значений, но сохранить их индексы в памяти.

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

Есть предложения по структуре данных или алгоритму?

Answer 1

Вам необходимо поместить данные и их исходный индекс в класс и определить сравнение таким образом, чтобы оно сравнивало только данные.

public class SortItemHelper implements Comparable<SortItemHelper>
{
    Data data;
    int originalIndex;

    public int compareTo(SortItemHelper other)
    {
        if (other == null)
            return 1;
        return data.compareTo(other.data);
    }
    ...
}

(Вы хотите сделать это универсальным для Data.)

Answer 2

Если кто-то ищет универсальную реализацию, я ее создал.

Базовый абстрактный класс:

public abstract class AbstractSortHelper<T> implements Comparable<AbstractSortHelper<T>> {
    protected final int index;
    protected final T data;

    public AbstractSortHelper(int index, T data) {
        this.index = index;
        this.data = data;
    }

    public int getIndex() {
        return index;
    }

    public T getData() {
        return data;
    }
}

Первый расширяемый класс, используемый для объектов, реализующих Comparable:

public class ComparableSortHelper<T extends Comparable> extends AbstractSortHelper<T> {

    public ComparableSortHelper(int index, T data) {
        super(index, data);
    }

    @Override
    public int compareTo(AbstractSortHelper<T> o) {
        return this.data.compareTo(o.data);
    }
}

Второй расширяющий класс, используемый для объектов, которые не реализуют Comparable.При использовании вам необходимо реализовать Comparator:

public abstract class ComparatorSortHelper<T> extends AbstractSortHelper<T> implements Comparator<T> {

    public ComparatorSortHelper(int index, T data) {
        super(index, data);
    }

    @Override
    public int compareTo(AbstractSortHelper<T> {
        return compare(this.data, o.data);
    }
}

Расширение ComparatorSortHelper выглядит следующим образом:

class DataSortHelper extends ComparatorSortHelper<Object[]> {

    public DataSortHelper(int index, Object[] data) {
        super(index, data);
    }

    @Override
    public int compare(Object[] o1, Object[] o2) {
        return Integer.compare((Integer) o1[0], (Integer) o2[0]);
    }
}

После использования сортировка выполняется просто:

List<DataSortHelper> list = new ArrayList<>();
// ...
Collections.sort(list);

Надеюсь, это кому-нибудь поможет.:)

Answer 3

Сделайте так, чтобы вы сортировали массив объектов (возможно, класса-оболочки вашего собственного дизайна), который знает свою собственную позицию).