сортировка вставок в односвязном списке - PullRequest
Новая
       11

сортировка вставок в односвязном списке

0 голосов
/ 28 марта 2011

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

Мое рассуждение: если предположить, что insertion sort по определению означает, что при перемещении вправо во внешнем цикле мы перемещаемся влево во внутреннем цикле и смещаем значения вверх (вправо) по мере необходимостии вставьте наше текущее значение, когда закончите с внутренним циклом.В результате SLL не может приспособить такой алгоритм.Правильно?

Ответы [ 3 ]

1 голос
/ 09 апреля 2012

Это выполнимо и интересная проблема для изучения.

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

Одиночный связанный список не может быть пройден назад, но вы всегда можете начать с его головы, чтобы искать позицию для нового элемента.

Сложность заключается в том, что при вставке узла i перед узлом j вы должны хорошо обрабатывать их отношения с соседями (я имею в виду, что нужно заботиться как о соседях узла i, так и о соседстве j).

1 голос
/ 23 января 2013

Вот мой код. Я надеюсь, что это полезно для вас. 

int insertSort(Node **pHead)
{
Node *current1 = (*pHead)->next;
Node *pre1 =*pHead;
Node *current2= *pHead;
Node *pre2=*pHead;
while(NULL!=current1)
    {
    pre2=*pHead;
    current2=*pHead;

    while((current2->data < current1->data))
    {
        pre2 = current2;
        current2 = current2->next;
    }
    if(current2 != current1)
    {
        pre1->next=current1->next;
        if(current2==*pHead)
        {
            current1->next=*pHead;
            *pHead = current1;
        }
        else
        {
            pre2->next = current1;
            current1->next = current2;
        }
        current1 = pre1->next;
    }
    else
    {
        pre1 = pre1->next;
        current1 = current1->next;
    }
}
return 0;

}

1 голос
/ 28 марта 2011

Ну, я бы звучал как Капитан Очевидность, но ответ в основном зависит от того, все ли у вас в порядке, когда все итерации направлены так же, как элементы, и все еще реализуете правильный алгоритм сортировки согласно вашему определению.Я действительно не хочу возиться с вашим определением сортировки вставок, поэтому боюсь, что вам действительно придется подумать самим.По крайней мере, какое-то время.В любом случае, это домашнее задание ...;)

Хорошо, вот что я получил перед закрытием страницы.Вы можете перебирать SLL в обратном направлении, но для посещения всех n элементов потребуется n * n / 2 обхода.Таким образом, вы теоретически в порядке с любыми направлениями обхода для ваших сортировочных циклов.Угадай, это в значительной степени решит твой вопрос.

...