Объединить Сортировать связанный список

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

11.08.2008 11:43:27
Angus Johnson 21.09.2017 00:18:03
18 ОТВЕТОВ

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

6
11.08.2008 13:57:59

Самое простое из «Алгоритмов Гоннет + Баеза Йейтс» . Вы называете это с нужным количеством отсортированных элементов, которые рекурсивно делятся пополам, пока не достигнет запроса на список первого размера, который вы затем просто снимаете с начала оригинального списка. Все они объединяются в полноразмерный отсортированный список.

[Обратите внимание, что в первом посте классная основанная на стеке запись называется Online Mergesort, и она упоминается в упражнении в Knuth Vol 3 как малейшее упоминание]

2
4.09.2008 09:22:26

Основано на ОТЛИЧНОМ коде с: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Подрезал немного, и привел в порядок:


typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list;  // Trivial case

    do { // For each power of two<=list length
        numMerges=0,left=list;tail=list=0; // Start at the start

        while (left) { // Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
            // Cut list into two halves (but don't overrun)
            while (right && leftSize<listSize) leftSize++,right=right->next;
            // Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
                // Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
                // Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
                // Sort prev pointer
                next->prev=tail; // Optional.
                tail=next;          
            }
            // Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
        // Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
    return list;
}

NB: Это гарантировано O (NLog (N)) и использует O (1) ресурсов (без рекурсии, без стека, ничего).

10
14.07.2012 19:19:27
Я думал, что попробую этот код в своем собственном связанном списке. По какой-то причине он работает медленнее, чем рекурсивная версия в списке из 10 миллионов элементов int. Это заняло около 6-7 секунд для рекурсивной версии и около 10 для этой?
Matt 18.07.2011 05:01:30
Не удивительно. Рекурсивный использует дополнительное хранилище, чтобы ускорить процесс.
Dave Gamble 8.04.2012 12:04:22

Более простой / более ясной реализацией может быть рекурсивная реализация, из которой время выполнения NLog (N) является более ясным.

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
    // some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
    // Trivial case.
    if (!list || !list->next)
        return list;

    aList *right = list,
          *temp  = list,
          *last  = list,
          *result = 0,
          *next   = 0,
          *tail   = 0;

    // Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next)
    {
        last = right;
        right = right->next;
        temp = temp->next->next;
    }

    // Break the list in two. (prev pointers are broken here, but we fix later)
    last->next = 0;

    // Recurse on the two smaller lists:
    list = merge_sort_list_recursive(list, compare);
    right = merge_sort_list_recursive(right, compare);

    // Merge:
    while (list || right)
    {
        // Take from empty lists, or compare:
        if (!right) {
            next = list;
            list = list->next;
        } else if (!list) {
            next = right;
            right = right->next;
        } else if (compare(list, right) < 0) {
            next = list;
            list = list->next;
        } else {
            next = right;
            right = right->next;
        }
        if (!result) {
            result=next;
        } else {
            tail->next=next;
        }
        next->prev = tail;  // Optional.
        tail = next;
    }
    return result;
}

NB. Это требование хранения журнала (N) для рекурсии. Производительность должна быть примерно сопоставима с другой стратегией, которую я опубликовал. Здесь возможна оптимизация путем запуска цикла слияния while (list && right) и простого добавления оставшегося списка (так как нас на самом деле не волнует конец списков; достаточно знать, что они объединены).

19
14.07.2012 19:27:52
public int[] msort(int[] a) {
    if (a.Length > 1) {
        int min = a.Length / 2;
        int max = min;

        int[] b = new int[min];
        int[] c = new int[max]; // dividing main array into two half arrays
        for (int i = 0; i < min; i++) {
            b[i] = a[i];
        }

        for (int i = min; i < min + max; i++) {
            c[i - min] = a[i];
        }

        b = msort(b);
        c = msort(c);

        int x = 0;
        int y = 0;
        int z = 0;

        while (b.Length != y && c.Length != z) {
            if (b[y] < c[z]) {
                a[x] = b[y];
                //r--
                x++;
                y++;
            } else {
                a[x] = c[z];
                x++;
                z++;
            }
        }

        while (b.Length != y) {
            a[x] = b[y];
            x++;
            y++;
        }

        while (c.Length != z) {
            a[x] = c[z];
            x++;
            z++;
        }
    }

    return a;
}
-3
14.07.2012 19:18:37
Прежде всего, ваш ответ нигде не совпадает с вопросом ОП. Во-вторых, не уверен, что вы комментируете?
Ravi 15.07.2017 15:30:47

Интересно, почему это должно быть большой проблемой, как указано здесь, вот простая реализация на Java без каких-либо «хитрых уловок».

//The main function
public static Node merge_sort(Node head) 
{
    if(head == null || head.next == null) 
        return head;

    Node middle = getMiddle(head);      //get the middle of the list
    Node left_head = head;
    Node right_head = middle.next; 
    middle.next = null;             //split the list into two halfs

    return merge(merge_sort(left_head), merge_sort(right_head));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
    Node dummyHead = new Node();

    for(Node current  = dummyHead; a != null && b != null; current = current.next;)
    {
        if(a.data <= b.data) 
        {
            current.next = a; 
            a = a.next; 
        }
        else
        { 
            current.next = b;
            b = b.next; 
        }

    }
    current.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public static Node getMiddle(Node head)
{
    if(head == null) 
        return head;

    Node slow = head, fast = head;

    while(fast.next != null && fast.next.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
85
4.01.2019 09:12:55
не-web.archive объяснение вместо устаревшей ссылки удалено в ревизии 4.
greybeard 20.05.2018 12:04:42

Вот моя реализация «сортировки слиянием списков» Кнута (алгоритм 5.2.4L от Vol.3 TAOCP, 2-е изд.). Я добавлю несколько комментариев в конце, но вот резюме:

При случайном вводе он работает немного быстрее, чем код Саймона Тэтхэма (см. Нерекурсивный ответ Дейва Гэмбла, со ссылкой), но немного медленнее, чем рекурсивный код Дейва Гэмбла. Это сложнее понять, чем либо. По крайней мере, в моей реализации требуется, чтобы каждый элемент имел ДВА указателя на элементы. (Альтернативой может быть один указатель и логический флаг.) Таким образом, это, вероятно, бесполезный подход. Тем не менее, одна отличительная черта заключается в том, что он работает очень быстро, если на входе есть длинные отрезки, которые уже отсортированы.

element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's Algorithm 5.2.4L "List merge sort"
     from Vol.3 of TAOCP, 2nd ed. */
  element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
  if(!list) return NULL;

L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
  head1.next=list;
  t=&head2;
  for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
    if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
  }
  t->next=NULL; t->spare=NULL; p->spare=NULL;
  head2.next=head2.spare;

L2: /* begin a new pass: */
  t=&head2;
  q=t->next;
  if(!q) return head1.next;
  s=&head1;
  p=s->next;

L3: /* compare: */
  if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
  if(s->next) s->next=p; else s->spare=p;
  s=p;
  if(p->next) { p=p->next; goto L3; } 
  else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
  s->next=q; s=t;
  for(qnext=q->next; qnext; q=qnext, qnext=q->next);
  t=q; q=q->spare;
  goto L8;
L6: /* add q onto the current end, s: */
  if(s->next) s->next=q; else s->spare=q;
  s=q;
  if(q->next) { q=q->next; goto L3; } 
  else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
  s->next=p;
  s=t;
  for(pnext=p->next; pnext; p=pnext, pnext=p->next);
  t=p; p=p->spare;
L8: /* is this end of the pass? */
  if(q) goto L3;
  if(s->next) s->next=p; else s->spare=p;
  t->next=NULL; t->spare=NULL;
  goto L2;
}
1
14.07.2012 19:19:08
Общая стратегия заключается в том, что у нас есть две цепочки подсписков, идущие от двух фиктивных элементов head1 и head2. Подсписок, как известно, отсортирован. Мы делаем несколько проходов, объединяя первый подсписок из head1 с первым из head2, затем второй со вторым и так далее. (Важно, чтобы в цепочке head1 было одинаковое количество подсписков или один дополнительный.) Недавно объединенные подсписки прикрепляются поочередно к первой и второй цепочке, на месте, стабильно и без рекурсии.
Ed Wynn 14.07.2012 19:18:50
Существенной особенностью этой реализации является то, что она использует второй указатель, e-> spare, с каждым элементом. До конца подсписка e-> next дает следующий элемент. В конце e-> next равно NULL. Начало следующего подсписка (если есть) дается e-> spare. В конце сортировки весь список связывается через -> Далее. Псевдокод Кнута использовал указатели массива вместо указателей, а отрицательный индекс объявлял конец подсписка (а абсолютное значение давало начало следующего подсписка).
Ed Wynn 14.07.2012 19:19:12
Шаг L1 организует входной список в подсписки. «Ванильная» версия начинается со всех подсписков длины 1. Здесь «умная» версия сохраняет все упорядоченные последовательности в списке ввода. В частности, если список отсортирован по прибытии, сортировка прекращается после (n-1) сравнений. Умная версия, следовательно, дает значительную экономию на отсортированном вводе и меньшую экономию на вводе, который имеет некоторый уклон к сортировке. При случайном вводе умная версия обычно немного быстрее (на пару процентов), хотя и использует больше сравнений.
Ed Wynn 14.07.2012 19:20:10
Как я сказал в начале, я не ожидаю, что кому-нибудь понравится это как алгоритм (если вы часто не сортируете почти идеально отсортированный список). Я добавил это (в довольно старый пост), чтобы избавить вас от неприятностей и разочарований, которые я только что пережил ;-)
Ed Wynn 14.07.2012 19:24:05

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

element* mergesort(element *head,long lengtho)
{ 
  long count1=(lengtho/2), count2=(lengtho-count1);
  element *next1,*next2,*tail1,*tail2,*tail;
  if (lengtho<=1) return head->next;  /* Trivial case. */

  tail1 = mergesort(head,count1);
  tail2 = mergesort(tail1,count2);
  tail=head;
  next1 = head->next;
  next2 = tail1->next;
  tail1->next = tail2->next; /* in case this ends up as the tail */
  while (1) {
    if(cmp(next1,next2)<=0) {
      tail->next=next1; tail=next1;
      if(--count1==0) { tail->next=next2; return tail2; }
      next1=next1->next;
    } else {
      tail->next=next2; tail=next2;
      if(--count2==0) { tail->next=next1; return tail1; }
      next2=next2->next;
    }
  }
}
2
15.07.2012 10:06:25
Я придумал, по сути, ту же реализацию, за исключением использования указателей на указатели вместо фиктивных узлов , ясно полагая, что мой инновационный код должен стать качественным скачком в компьютерной науке. Полагаю, ничего нового под солнцем. Какие-нибудь предложения для чистого способа ускорения в основном предварительно отсортированного случая?
doynax 6.01.2014 07:35:16

В моно eglib есть нерекурсивная слияние связанных списков .

Основная идея заключается в том, что цикл управления для различных слияний параллелен побитному приращению двоичного целого числа. Существует O (n) слияний для «вставки» n узлов в дерево слияний, и ранг этих слияний соответствует двоичной цифре, которая увеличивается. Используя эту аналогию, только O (log n) узлов дерева слияния должны быть материализованы во временный массив хранения.

1
15.08.2013 05:34:58
Это лучшая реализация, которую я нашел до сих пор, сделал ее переносимой (которая может быть включена напрямую, с добавлением thunkаргумента optiona ~ like qsort_r). См gist.github.com/ideasman42/...
ideasman42 10.06.2015 13:17:03

Я был одержим оптимизацией беспорядка для этого алгоритма, и вот то, к чему я наконец пришел. Много другого кода в Интернете и StackOverflow ужасно плохо. Есть люди, пытающиеся получить среднюю точку списка, выполняющие рекурсию, имеющие несколько циклов для оставшихся узлов, сохраняющие множество вещей - ВСЕ из которых не нужны. MergeSort естественным образом подходит для связанного списка, и алгоритм может быть красивым и компактным, но не так просто добраться до этого состояния.

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

Обратите внимание, что этот ответ объединяет несколько методов из другого ответа https://stackoverflow.com/a/3032462/207661 . Пока код написан на C #, его легко конвертировать в C ++, Java и т. Д.

SingleListNode<T> SortLinkedList<T>(SingleListNode<T> head) where T : IComparable<T>
{
    int blockSize = 1, blockCount;
    do
    {
        //Maintain two lists pointing to two blocks, left and right
        SingleListNode<T> left = head, right = head, tail = null;
        head = null; //Start a new list
        blockCount = 0;

        //Walk through entire list in blocks of size blockCount
        while (left != null)
        {
            blockCount++;

            //Advance right to start of next block, measure size of left list while doing so
            int leftSize = 0, rightSize = blockSize;
            for (;leftSize < blockSize && right != null; ++leftSize)
                right = right.Next;

            //Merge two list until their individual ends
            bool leftEmpty = leftSize == 0, rightEmpty = rightSize == 0 || right == null;
            while (!leftEmpty || !rightEmpty)
            {
                SingleListNode<T> smaller;
                //Using <= instead of < gives us sort stability
                if (rightEmpty || (!leftEmpty && left.Value.CompareTo(right.Value) <= 0))
                {
                    smaller = left; left = left.Next; --leftSize;
                    leftEmpty = leftSize == 0;
                }
                else
                {
                    smaller = right; right = right.Next; --rightSize;
                    rightEmpty = rightSize == 0 || right == null;
                }

                //Update new list
                if (tail != null)
                    tail.Next = smaller;
                else
                    head = smaller;
                tail = smaller;
            }

            //right now points to next block for left
            left = right;
        }

        //terminate new list, take care of case when input list is null
        if (tail != null)
            tail.Next = null;

        //Lg n iterations
        blockSize <<= 1;

    } while (blockCount > 1);

    return head;
}

Точки интереса

  • Не требуется специальной обработки для случаев, таких как нулевой список из списка 1 и т. Д. Эти случаи "просто работают".
  • Во многих текстах «стандартных» алгоритмов есть два цикла для обхода оставшихся элементов для обработки случая, когда один список короче другого. Выше код устраняет необходимость в этом.
  • Мы уверены, что сортировка стабильна
  • Внутренний цикл while, который является горячей точкой, оценивает в среднем 3 выражения на одну итерацию, что я считаю минимальным.

Обновление: @ ideasman42 перевел вышеприведенный код на C / C ++ вместе с предложениями по исправлению комментариев и еще большим улучшением. Выше код теперь актуален с этим.

2
23.05.2017 11:47:26
Это абсолютно великолепно! Я преобразовал его в Delphi, и он работает очень хорошо. Спасибо, сэр !
Marus Nebunu 7.05.2015 11:43:43
Комментарии выглядят так, как будто они не обновлены в соответствии с кодом. Они ссылаются на переменные, которых нет в коде, p q & kкоторые (я думаю) должны быть left right & block_sizeсоответственно.
ideasman42 23.05.2015 05:30:50
Сделал улучшенную версию этого ответа: gist.github.com/ideasman42/5921b0edfc6aa41a9ce0 1) Используйте указатель на хвост (уберите 2х условных проверок, уменьшите размер кода). 2) Избегайте переназначения пустых значений, размер которых не изменяется. 3) Исправлены комментарии.
ideasman42 23.05.2015 06:12:02
Спасибо @ ideaman42. Я добавил одно улучшение в коде выше. Для tail_p не существует прямого эквивалента C #, поэтому он остается прежним :(.
Shital Shah 24.05.2015 11:08:14
Хотя это довольно хорошо, версия от eglib преформ Mono слегка быстрее в моих тестах (оптимизированный C) ~ 10-20%, см: stackoverflow.com/a/18246901/432509
ideasman42 10.06.2015 13:17:54

Я решил проверить здесь примеры, а также еще один подход, первоначально написанный Джонатаном Каннингемом в Pop-11. Я закодировал все подходы в C # и провел сравнение с рядом разных размеров списков. Я сравнил подход Mono eglib от Raja R Harinath, код C # от Shital Shah, подход Java от Jayadev, рекурсивные и нерекурсивные версии от David Gamble, первый код C от Ed Wynn (этот сбой произошел с моим примером набора данных, Я не отлаживал) и версию Каннингема. Полный код здесь: https://gist.github.com/314e572808f29adb0e41.git .

Mono eglib основан на идее Каннингема и имеет сравнимую скорость, если только список не отсортирован, и в этом случае подход Каннингема гораздо быстрее (если он частично отсортирован, eglib немного быстрее). Код eglib использует фиксированную таблицу для хранения рекурсии сортировки слиянием, тогда как подход Каннингема работает с использованием повышающихся уровней рекурсии - поэтому он начинается без рекурсии, затем рекурсии с 1 глубиной, затем рекурсии с 2 глубинами и так далее, в соответствии с сколько шагов нужно, чтобы сделать сортировку. Я нахожу код Каннингема немного легче следовать, и нет никаких сомнений в том, насколько велика составление таблицы рекурсии, поэтому он получает мой голос. Другие подходы, которые я пробовал на этой странице, были в два или более раз медленнее.

Вот порт C # типа Pop-11:

/// <summary>
/// Sort a linked list in place. Returns the sorted list.
/// Originally by Jonathan Cunningham in Pop-11, May 1981.
/// Ported to C# by Jon Meyer.
/// </summary>
public class ListSorter<T> where T : IComparable<T> {
    SingleListNode<T> workNode = new SingleListNode<T>(default(T));
    SingleListNode<T> list;

    /// <summary>
    /// Sorts a linked list. Returns the sorted list.
    /// </summary>
    public SingleListNode<T> Sort(SingleListNode<T> head) {
        if (head == null) throw new NullReferenceException("head");
        list = head;

        var run = GetRun(); // get first run
        // As we progress, we increase the recursion depth. 
        var n = 1;
        while (list != null) {
            var run2 = GetSequence(n);
            run = Merge(run, run2);
            n++;
        }
        return run;
    }

    // Get the longest run of ordered elements from list.
    // The run is returned, and list is updated to point to the
    // first out-of-order element.
    SingleListNode<T> GetRun() {
        var run = list; // the return result is the original list
        var prevNode = list;
        var prevItem = list.Value;

        list = list.Next; // advance to the next item
        while (list != null) {
            var comp = prevItem.CompareTo(list.Value);
            if (comp > 0) {
                // reached end of sequence
                prevNode.Next = null;
                break;
            }
            prevItem = list.Value;
            prevNode = list;
            list = list.Next;
        }
        return run;
    }

    // Generates a sequence of Merge and GetRun() operations.
    // If n is 1, returns GetRun()
    // If n is 2, returns Merge(GetRun(), GetRun())
    // If n is 3, returns Merge(Merge(GetRun(), GetRun()),
    //                          Merge(GetRun(), GetRun()))
    // and so on.
    SingleListNode<T> GetSequence(int n) {
        if (n < 2) {
            return GetRun();
        } else {
            n--;
            var run1 = GetSequence(n);
            if (list == null) return run1;
            var run2 = GetSequence(n);
            return Merge(run1, run2);
        }
    }

    // Given two ordered lists this returns a list that is the
    // result of merging the two lists in-place (modifying the pairs
    // in list1 and list2).
    SingleListNode<T> Merge(SingleListNode<T> list1, SingleListNode<T> list2) {
        // we reuse a single work node to hold the result.
        // Simplifies the number of test cases in the code below.
        var prevNode = workNode;
        while (true) {
            if (list1.Value.CompareTo(list2.Value) <= 0) {
                // list1 goes first
                prevNode.Next = list1;
                prevNode = list1;
                if ((list1 = list1.Next) == null) {
                    // reached end of list1 - join list2 to prevNode
                    prevNode.Next = list2;
                    break;
                }
            } else {        // same but for list2
                prevNode.Next = list2;
                prevNode = list2;
                if ((list2 = list2.Next) == null) {
                    prevNode.Next = list1;
                    break;
                }
            }
        }

        // the result is in the back of the workNode
        return workNode.Next;
    }
}
2
25.11.2015 22:59:35
Метод mono eglib похож на тот, который я опубликовал в своем ответе, и оба по сути такие же, как HP / Microsoft STL std :: list :: sort (). В примере с mono eglib таблица «рекурсия» переворачивается, ранг [i] указывает на пробег длины 2 до степени i, за исключением того, что последний ранг записи [MAX_RANKS-1] указывает на список неограниченного размера и добавляется путем слияния прогонов длины 2 в степень (MAX_RANK-2). MAX_RANK от 26 до 32 более чем достаточно.
rcgldr 25.02.2016 00:27:58
Аналогичная стратегия используется в функции суммирования с плавающей запятой, где массив частичных сумм, проиндексированных показателем числа с плавающей запятой, используется для хранения частичных сумм, так что добавляются только значения с одинаковыми показателями до тех пор, пока не настанет время вернуть полная сумма путем суммирования значений в массиве от наименьшего к наибольшему. Я не уверен, что было изобретено первым, функция суммирования или сортировка слиянием связанного списка.
rcgldr 25.02.2016 00:32:42

Другой пример нерекурсивной сортировки слиянием для связанных списков, где функции не являются частью класса. Этот пример кода и HP / Microsoft std :: list :: sort оба используют один и тот же базовый алгоритм. Восходящая нерекурсивная сортировка слиянием, которая использует небольшой (от 26 до 32) массив указателей на первые узлы списка, где массив [i] равен либо 0, либо указывает на список размера 2 в степени i , В моей системе Intel 2600K 3,4 ГГц она может сортировать 4 миллиона узлов с 32-разрядными целыми числами без знака в качестве данных примерно за 1 секунду.

NODE * MergeLists(NODE *, NODE *); /* prototype */

/* sort a list using array of pointers to list       */
/* aList[i] == NULL or ptr to list with 2^i nodes    */

#define NUMLISTS 32             /* number of lists */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];         /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)           /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)   /* init array */
        aList[i] = NULL;
    pNode = pList;              /* merge nodes into array */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)   /* don't go beyond end of array */
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;           /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}

/* merge two already sorted lists                    */
/* compare uses pSrc2 < pSrc1 to follow the STL rule */
/*   of only using < and not <=                      */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;          /* destination head ptr */
NODE **ppDst = &pDst;       /* ptr to head or prev->next */
    if(pSrc1 == NULL)
        return pSrc2;
    if(pSrc2 == NULL)
        return pSrc1;
    while(1){
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            if(pSrc2 == NULL){
                *ppDst = pSrc1;
                break;
            }
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            if(pSrc1 == NULL){
                *ppDst = pSrc2;
                break;
            }
        }
    }
    return pDst;
}
1
25.02.2016 00:29:10

Это весь кусок кода, который показывает, как мы можем создать список ссылок в Java и отсортировать его с помощью сортировки слиянием. Я создаю узел в классе MergeNode, и есть другой класс MergesortLinklist, где есть логика деления и слияния.

class MergeNode {
    Object value;
    MergeNode next;

    MergeNode(Object val) {
        value = val;
        next = null;

    }

    MergeNode() {
        value = null;
        next = null;

    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public MergeNode getNext() {
        return next;
    }

    public void setNext(MergeNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "MergeNode [value=" + value + ", next=" + next + "]";
    }

}

public class MergesortLinkList {
    MergeNode head;
    static int totalnode;

    public MergeNode getHead() {
        return head;
    }

    public void setHead(MergeNode head) {
        this.head = head;
    }

    MergeNode add(int i) {
        // TODO Auto-generated method stub
        if (head == null) {
            head = new MergeNode(i);
            // System.out.println("head value is  "+head);
            return head;

        }
        MergeNode temp = head;

        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new MergeNode(i);
        return head;

    }

    MergeNode mergesort(MergeNode nl1) {
        // TODO Auto-generated method stub

        if (nl1.next == null) {
            return nl1;
        }

        int counter = 0;

        MergeNode temp = nl1;

        while (temp != null) {
            counter++;
            temp = temp.next;

        }
        System.out.println("total nodes  " + counter);

        int middle = (counter - 1) / 2;

        temp = nl1;
        MergeNode left = nl1, right = nl1;
        int leftindex = 0, rightindex = 0;

        if (middle == leftindex) {
            right = left.next;
        }
        while (leftindex < middle) {

            leftindex++;
            left = left.next;
            right = left.next;
        }

        left.next = null;
        left = nl1;

        System.out.println(left.toString());
        System.out.println(right.toString());

        MergeNode p1 = mergesort(left);
        MergeNode p2 = mergesort(right);

        MergeNode node = merge(p1, p2);

        return node;

    }

    MergeNode merge(MergeNode p1, MergeNode p2) {
        // TODO Auto-generated method stub

        MergeNode L = p1;
        MergeNode R = p2;

        int Lcount = 0, Rcount = 0;

        MergeNode tempnode = null;

        while (L != null && R != null) {

            int val1 = (int) L.value;

            int val2 = (int) R.value;

            if (val1 > val2) {

                if (tempnode == null) {
                    tempnode = new MergeNode(val2);
                    R = R.next;
                } else {

                    MergeNode store = tempnode;

                    while (store.next != null) {
                        store = store.next;
                    }
                    store.next = new MergeNode(val2);

                    R = R.next;
                }

            } else {
                if (tempnode == null) {
                    tempnode = new MergeNode(val1);
                    L = L.next;
                } else {

                    MergeNode store = tempnode;

                    while (store.next != null) {
                        store = store.next;
                    }
                    store.next = new MergeNode(val1);

                    L = L.next;
                }

            }

        }

        MergeNode handle = tempnode;

        while (L != null) {

            while (handle.next != null) {

                handle = handle.next;

            }
            handle.next = L;

            L = null;

        }

        // Copy remaining elements of L[] if any
        while (R != null) {
            while (handle.next != null) {

                handle = handle.next;

            }
            handle.next = R;

            R = null;

        }

        System.out.println("----------------sorted value-----------");
        System.out.println(tempnode.toString());
        return tempnode;
    }

    public static void main(String[] args) {
        MergesortLinkList objsort = new MergesortLinkList();
        MergeNode n1 = objsort.add(9);
        MergeNode n2 = objsort.add(7);
        MergeNode n3 = objsort.add(6);
        MergeNode n4 = objsort.add(87);
        MergeNode n5 = objsort.add(16);
        MergeNode n6 = objsort.add(81);

        MergeNode n7 = objsort.add(21);
        MergeNode n8 = objsort.add(16);

        MergeNode n9 = objsort.add(99);
        MergeNode n10 = objsort.add(31);

        MergeNode val = objsort.mergesort(n1);

        System.out.println("===============sorted values=====================");
        while (val != null) {
            System.out.println(" value is  " + val.value);
            val = val.next;
        }
    }

}
0
21.05.2017 09:11:49

Я не вижу никаких решений C ++, размещенных здесь. Итак, вот и все. Надеюсь, это поможет кому-то.

class Solution {
public:
    ListNode *merge(ListNode *left, ListNode *right){
        ListNode *head = NULL, *temp = NULL;
        // Find which one is the head node for the merged list
        if(left->val <= right->val){
            head = left, temp = left;
            left = left->next;
        }
        else{
            head = right, temp = right;
            right = right->next;
        }
        while(left && right){
            if(left->val <= right->val){
                temp->next = left;
                temp = left;
                left = left->next;
            }
            else{
                temp->next = right;
                temp = right;
                right = right->next;
            }
        }
        // If some elements still left in the left or the right list
        if(left)
            temp->next = left;
        if(right)
            temp->next = right;
        return head;
    }

    ListNode* sortList(ListNode* head){
        if(!head || !head->next)
            return head;

        // Find the length of the list
        int length = 0;
        ListNode *temp = head;
        while(temp){
            length++;
            temp = temp->next;
        }
        // Reset temp
        temp = head;
        // Store half of it in left and the other half in right
        // Create two lists and sort them
        ListNode *left = temp, *prev = NULL;
        int i = 0, mid = length / 2;
        // Left list
        while(i < mid){
            prev = temp;
            temp = temp->next;
            i++;
        }
        // The end of the left list should point to NULL
        if(prev)
            prev->next = NULL;
        // Right list
        ListNode  *right = temp;
        // Sort left list
        ListNode *sortedLeft = sortList(left);
        // Sort right list
        ListNode *sortedRight = sortList(right);
        // Merge them
        ListNode *sortedList = merge(sortedLeft, sortedRight);
        return sortedList;
    }
};
0
14.08.2018 00:08:49

Вот Java-реализация сортировки слиянием в связанном списке:

  • Сложность времени: O (n.logn)
  • Сложность пространства: O (1) - реализация сортировки слиянием в связанном списке позволяет избежать затрат на вспомогательное хранение O (n), обычно связанных с алгоритмом
class Solution
{
    public ListNode mergeSortList(ListNode head) 
    {
        if(head == null || head.next == null)
            return head;

        ListNode mid = getMid(head), second_head = mid.next; mid.next = null;

        return merge(mergeSortList(head), mergeSortList(second_head));
    }

    private ListNode merge(ListNode head1, ListNode head2)
    {
        ListNode result = new ListNode(0), current = result;

        while(head1 != null && head2 != null)
        {
            if(head1.val < head2.val)
            {
                current.next = head1;
                head1 = head1.next;
            }
            else
            {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }

        if(head1 != null) current.next = head1;
        if(head2 != null) current.next = head2;

        return result.next;
    }

    private ListNode getMid(ListNode head)
    {
        ListNode slow = head, fast = head.next;

        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
0
1.01.2019 14:35:25
while(fast != null && fast.next != null), это не вызывает бесконечную рекурсию для списка, который имеет только 2 элемента?
Rick 4.01.2019 09:11:56

Проверенная, рабочая C++версия единого связного списка, основанная на ответе с наибольшим количеством голосов .

singlelinkedlist.h:

#pragma once
#include <stdexcept>
#include <iostream>
#include <initializer_list>
namespace ythlearn{
    template<typename T>
    class Linkedlist{
    public:
        class Node{
        public:
            Node* next;
            T elem;
        };
        Node head;
        int _size;
    public:
        Linkedlist(){
            head.next = nullptr;            
            _size = 0;
        }

        Linkedlist(std::initializer_list<T> init_list){
            head.next = nullptr;            
            _size = 0;
            for(auto s = init_list.begin(); s!=init_list.end(); s++){
                push_left(*s);
            }
        }

        int size(){
            return _size;
        }

        bool isEmpty(){
            return size() == 0;
        }

        bool isSorted(){
            Node* n_ptr = head.next;
            while(n_ptr->next != nullptr){
                if(n_ptr->elem > n_ptr->next->elem)
                    return false;
                n_ptr = n_ptr->next;
            }
            return true;
        }

        Linkedlist& push_left(T elem){
            Node* n = new Node;
            n->elem = elem;
            n->next = head.next;
            head.next = n;
            ++_size;
            return *this;
        }

        void print(){
                Node* loopPtr = head.next;
                while(loopPtr != nullptr){
                    std::cout << loopPtr->elem << " ";
                    loopPtr = loopPtr->next;
                }
                std::cout << std::endl;
        }

        void call_merge(){
            head.next = merge_sort(head.next);
        }

        Node* merge_sort(Node* n){
            if(n == nullptr || n->next == nullptr)
                return n;
            Node* middle = getMiddle(n);
            Node* left_head = n;
            Node* right_head = middle->next;
            middle->next = nullptr;
            return merge(merge_sort(left_head), merge_sort(right_head));
        }

        Node* getMiddle(Node* n){
            if(n == nullptr)
                return n;
            Node* slow, *fast;
            slow = fast = n;
            while(fast->next != nullptr && fast->next->next != nullptr){
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }

        Node* merge(Node* a, Node* b){
            Node dummyHead;
            Node* current = &dummyHead;
            while(a != nullptr && b != nullptr){
                if(a->elem < b->elem){
                    current->next = a;
                    a = a->next;
                }else{
                    current->next = b;
                    b = b->next;
                }
                current = current->next;
            }
            current->next = (a == nullptr) ? b : a;
            return dummyHead.next;
        }

        Linkedlist(const Linkedlist&) = delete;
        Linkedlist& operator=(const Linkedlist&) const = delete;
        ~Linkedlist(){
            Node* node_to_delete;
            Node* ptr = head.next;
            while(ptr != nullptr){
                node_to_delete = ptr;
                ptr = ptr->next;
                delete node_to_delete;
            }

        }

    };
}

main.cpp:

#include <iostream>
#include <cassert>
#include "singlelinkedlist.h"
using namespace std;
using namespace ythlearn;

int main(){
    Linkedlist<int> l = {3,6,-5,222,495,-129,0};
    l.print();
    l.call_merge();
    l.print();
    assert(l.isSorted());
    return 0;
}
0
4.01.2019 09:06:14

Простейшая реализация Java:

Сложность времени: O (nLogn) n = количество узлов. Каждая итерация по связанному списку удваивает размер отсортированных меньших связанных списков. Например, после первой итерации связанный список будет отсортирован на две половины. После второй итерации связанный список будет отсортирован на четыре половины. Он будет продолжать сортировку по размеру связанного списка. Для достижения первоначального размера связанного списка потребуется O (logn) удвоений размеров небольших связанных списков. N в nlogn есть, потому что каждая итерация связанного списка займет время, пропорциональное количеству узлов в исходном связанном списке.

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
    }
}

class LinkedList {
    Node head;
    public Node mergesort(Node head) {
          if(head == null || head.next == null) return head;
          Node middle = middle(head), middle_next = middle.next;
          middle.next = null;
          Node left = mergesort(head), right = mergesort(middle_next), node = merge(left, right);
          return node;
    } 

    public Node merge(Node first, Node second) {
          Node node = null;
          if (first == null) return second;
          else if (second == null) return first;
          else if (first.data <= second.data) {
              node = first;
              node.next = merge(first.next, second);

          } else {
              node = second;
              node.next = merge(first, second.next);
          }
          return node;
    }

    public Node middle(Node head) {
          if (head == null) return head;
          Node second = head, first = head.next;
          while(first != null) {
              first = first.next;
              if (first != null) {
                 second = second.next;
                 first = first.next;
              }
          }
          return second;
    }

}
0
21.05.2019 15:00:08

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

Код на F #, но будет на любом языке. Поскольку это необычный язык семейства ML, я дам несколько слов для улучшения читабельности. F # вложенность осуществляется путем табулирования. последняя строка кода в функции (вложенная часть) - это возвращаемое значение. (x, y) - кортеж, x :: xs - список заголовка x и хвоста xs (где xs может быть пустым), |> принимает результат последней строки и передает его в качестве аргумента в выражение справа от него (улучшение читаемости) и last (забавные аргументы -> некоторое выражение) являются лямбда-функцией.

// split the list into a singleton list
let split list = List.map (fun x -> [x]) lst

// takes to list and merge them into a sorted list
let sort lst1 lst2 =
   // nested function to hide accumulator
   let rec s acc pair =
       match pair with
       // empty list case, return the sorted list
       | [], [] -> List.rev acc
       | xs, [] | [], xs ->
          // one empty list case, 
          // append the rest of xs onto acc and return the sorted list
          List.fold (fun ys y -> y :: ys) acc xs
          |> List.rev
       // general case
       | x::xs, y::ys ->
          match x < y with
          | true -> // cons x onto the accumulator
              s (x::acc) (xs,y::ys)
          | _ ->
              // cons y onto the accumulator
              s (y::acc) (x::xs,ys)

    s [] (lst1, lst2)  

let msort lst =
  let rec merge acc lst =
      match lst with
      | [] ->
          match acc with
          | [] -> [] // empty list case
          | _ -> merge [] acc
      | x :: [] -> // single list case (x is a list)
         match acc with
         | [] -> x // since acc are empty there are only x left, hence x are the sorted list.
         | _ -> merge [] (x::acc) // still need merging.
       | x1 :: x2 :: xs ->
           // merge the lists x1 and x2 and add them to the acummulator. recursiv call
           merge (sort x1 x2 :: acc) xs

   // return part
   split list // expand to singleton list list
   |> merge [] // merge and sort recursively.

Важно отметить, что это полностью хвостовая рекурсия, поэтому нет возможности переполнения стека, и, сначала расширяя список до одноэлементного списка за один раз, мы уменьшаем постоянный коэффициент на худшую стоимость. Поскольку слияние работает со списком списков, мы можем рекурсивно объединять и сортировать внутренний список, пока не доберемся до точки исправления, где весь внутренний список отсортирован в один список, а затем мы вернем этот список, следовательно, сворачивание из списка в список очередной раз.

0
29.01.2020 08:53:56