Алгоритмы сортировки с двусвязными списками

Question

Мне нужно реализовать четыре алгоритма сортировки (Вставка, Выбор, Оболочка, Быстрая сортировка) с двусвязным списком в качестве домашней работы, но я полностью потерян, потому что все объяснения этих алгоритмов сортировки, которые я нашел в Интернете, требуют использования массивов. Я попытался использовать этот код в качестве псевдоиндекса для моей DLL:

public DoubleNode this[int num]
    {
        get
        {
            DoubleNode x = head;
            for(int k = 0; k < num; k++)
                x = x.Next;

            return x;
        }
    }

Но этого недостаточно, потому что это не сеттер. Есть идеи, парни / девушки?

Answer 1

ОК (на основании моего комментария) один пример - вставка - см .: http://en.wikipedia.org/wiki/Insertion_sort#List_insertion_sort_code_in_C.2B.2B - сортировка вставки на самом деле более подходит для отображения, чем для массивов (поскольку операция вставки в массив означает перемещение элементов).

То же самое относится к быстрой сортировке http://en.wikipedia.org/wiki/Quicksort#Simple_version

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

Сортировка оболочки основана на сортировке вставкой и не должна быть слишком сложной для реализации на основе этой идеи.