Как отсортировать непересекающийся подсписок?

Question

Допустим, у меня есть следующий список: [2, 1, 4, 6, 3, 7]. У меня также есть метод, который сортирует любой список. Однако я хочу выполнить сортировку только по элементам с индексами 1, 2 и 4, то есть подсписком [1, 4, 3]. Сортировка по этому подсписку производит [1, 3, 4]. Как получить исходный список таким образом, чтобы я сортировал только по индексам 1, 2 и 4, т.е. [2, 1, 3, 6, 4, 7]?

Answer 1

Самый простой способ - использовать дополнительный уровень косвенности. Например, создайте список (здесь подразумевается просто линейная коллекция, не обязательно связанный список) индексов трех элементов, которые вы хотите отсортировать, и код для сравнения / обмена через этот уровень косвенности.

Answer 2

Следующий код Python делает эту работу.Он может отличаться от принятого ответа Джерри Коффинса: вместо того, чтобы сортировать по косвенным путям, он извлекает значения, сортирует, а затем вставляет их обратно.

data    = [7, 6, 5, 4, 3, 2, 1, 0]
indices = sorted([1,2,4])
values  = [data[i] for i in indices] # [6, 5, 3]
values.sort()                        # [3, 5, 6]
for index, value in zip(indices, values):
    data[index] = value
print (data)                         # [7, 3, 5, 4, 6, 2, 1, 0]

1. Исходные индексы должны быть отсортированы, чтобы все работало.1005 *

2. Извлекаются соответствующие значения.

3. Значения отсортированы.

4. Цикл for выводит отсортированные значенияобратно в исходный массив.

Answer 3

Благодаря предложению Джерри Коффина, вот решение на Java для тех, кто заинтересован:

import java.util.List;
import java.util.AbstractList;
import java.util.Arrays;

public class ExtendedSubList<E> extends AbstractList<E>
{
    protected final List<E> parent;
    protected final int[] indices;

    public static <E> List<E> subList(final List<E> parent, int ... indices)
    {
        if (parent == null)
            throw new IllegalArgumentException("parent == null");
        if (indices == null)
            throw new IllegalArgumentException("indices == null");
        for (int i = 0; i < indices.length; i++)
            if (!(0 <= indices[i] && indices[i] < parent.size()))
                throw new IllegalArgumentException(String.format("index %d (at position %d) is not in bounds", indices[i], i));
        Arrays.sort(indices);
        return new ExtendedSubList(parent, indices);
    }

    protected ExtendedSubList(List<E> parent, int[] indices)
    {
        this.parent = parent;
        this.indices = indices;
    }

    public E get(int index)
    {
        return parent.get(indices[index]);
    }
    public int size()
    {
        return indices.length;
    }

    public E set(int index, E element)
    {
        return parent.set(indices[index], element);
    }
}

Пример использования:

List<Integer> list = Arrays.asList(2, 1, 4, 6, 3, 7);
Collections.sort(ExtendedSubList.subList(list), 1, 2, 4);

В результате получается список: [2, 1, 3, 6, 4, 7].