Algorithmus Gymnastik 16

Merge Sort Die Zusammenführungssortierung ist einer der bekanntesten Sortieralgorithmen, die Divide & Conquer verwenden. Es ist ein Sortieralgorithmus, der versucht, die Sortierung durch rekursives Teilen und erneutes Zusammenführen zu realisieren. Dieses Mal möchte ich diese Zusammenführungssortierung verwenden, um die verknüpfte Liste anstelle des Arrays zu sortieren.

Beispiel

Solution

Runtime Complexity O(n(log(n)) Das Zusammenführen mit n Listen dauert proportional zu n. (verschmelzen) Außerdem dauert es log (n) Zeit, um n Daten in zwei Teile zu teilen. (Teilen) Daher ist die Ausführungszeit O (n log (n)). Memory Complexity O（log n) Die Verwendung der Wiederholung verbraucht Speicher auf dem Stapel, was zu O (log n) führt.

Der Teilungsschritt teilt die eingegebene Liste in zwei Hälften und fährt mit einer Liste der Größe 1 oder 0 fort. Der Join-Schritt führt die sortierten Listen zusammen und wird fortgesetzt, bis die Listen vollständig sortiert sind. Die rekursive Beziehung dieses Zusammenführungssortieralgorithmus ist wie folgt:

T（n）= 2T（n / 2）+ n

Diese Formel wird bei der Analyse der Laufzeitkomplexität des rekursiven Algorithmus verwendet, z. B. in Universitätsklassen. Da es sich um einen zu behandelnden Inhalt handelt, werde ich nicht auf so viel eingehen, aber wenn Sie interessiert sind, klicken Sie hier Referenz. ).

Denkweise

Da die Zusammenführungssortierung für die Liste und nicht für das Array durchgeführt wird, werden die Verknüpfungen benachbarter Knoten beim Teilen ausgeführt Ich werde es schneiden. Dann fühlt es sich an, als würde man einen Knoten miteinander vergleichen und beim Zusammenführen neu anordnen. Die Implementierung kann etwas verwirrend sein, da sie Wiederholungen verwendet. Die Idee ist, dass es drei Methoden gibt. Verwenden Sie die erste mergeSort-Methode, um eine grobe Aufteilung und Zusammenführung von Logikrahmen zu erstellen. Dann ist die zweite splitHalf-Methode eine Teilungsrolle, die die Aufgabe hat, den Link zu teilen. Fügen Sie die Köpfe der beiden Teilungslisten in das Paarobjekt ein. Die dritte mergeSortedList-Methode ist die Zusammenführungsrolle, die für das Zusammenführen und Neuanordnen der geteilten Knoten verantwortlich ist.

Implementierung

MergeSort.java

class MergeSort{

    public LinkedListNode mergeSort(LinkedListNode head) {

      // base case
      if (head == null || head.next == null) {
        return head;
      }

      Pair<LinkedListNode, LinkedListNode> pair = new Pair<LinkedListNode, LinkedListNode>(null, null);
      
      // Let's split the list in half, sort the sublists
      // and then merge the sorted lists.

      splitHalf(head, pair);

      pair.first = mergeSort(pair.first);
      pair.second = mergeSort(pair.second);

      return mergeSortedList(pair.first, pair.second);
  }
    // this method splits linked list in two halves by iterating over whole list
    // It returns head pointers of first and 2nd halves of linked lists in pair
    // Head of 1st half is just the head node of linked list
   public void splitHalf(LinkedListNode head, Pair<LinkedListNode, LinkedListNode> pair) {
      
      if (head == null) {
        return;
      }

      if (head.next == null) {
        pair.first = head;
        pair.second = null;
      } else {
        
        LinkedListNode slow = head;
        LinkedListNode fast = head.next;

      // Two pointers, 'fast' and 'slow'. 'fast' will move two steps in each 
      // iteration whereas 'slow' will be pointing to the middle element
      // at the end of the loop
        while (fast != null) {

          fast = fast.next;

          if(fast != null) {
            fast = fast.next;
            slow = slow.next;
          }
        }

        pair.first = head;
        pair.second = slow.next;

        // disconnecting the first linked list with the second one
        slow.next = null;
      }
    }
    public LinkedListNode mergeSortedList(LinkedListNode first, LinkedListNode second) {
      
      if (first == null) {
        return second;
      }

      if (second == null){
        return first;
      }

      LinkedListNode newHead;

      if (first.data <= second.data) {
        newHead = first;
        first = first.next;
      } else {
        newHead = second;
        second = second.next;
      }

      LinkedListNode current = newHead;

      while (first != null && second != null) {
        LinkedListNode temp = null;
        if (first.data <= second.data) {
          temp = first;
          first = first.next;
        } else {
          temp = second;
          second = second.next;
        }

        current.next = temp;
        current = current.next;
      }

      if (first != null) {
        current.next = first;
      } else if (second != null) {
        current.next = second;
      }

      return newHead;
    }
}

Output So sortiert!