Radix Sortierung in einfach verknüpften Liste C#

Question

Ich versuche, eine Radix-Sortierung in einer Linked-List-Klasse zu tun. Ich habe den Radix-Sortieralgorithmus für Array gefunden und versuche, ihn zu ändern, um mit meiner verknüpften Liste zu arbeiten. Ich kämpfe jedoch ein bisschen. Der Code, den ich ändern möchte, wurde von http://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-10.php übernommen. Ich habe den Code mit einem Array getestet und es hat funktioniert. Hat jemand irgendwelche Ideen, wie man Radix-Sort-Arbeit in einer verketteten Liste macht?

// abstrakte Klasse

abstract class DataList 
{ 
    protected int length; 
    public int Length { get { return length; } } 
    public abstract double Head(); 
    public abstract double Next(); 
    public abstract void Swap(int a, int b); 
    public void Print(int n) 
    { 
     Console.Write("{0} ", Head()); 
     for (int i = 1; i < n; i++) 
      Console.Write("{0} ", Next()); 
     Console.WriteLine(); 
    } 
} 

// verketteten Liste Klasse

class LinkedList : DataList 
{ 
    class MyLinkedListNode 
    { 
     public MyLinkedListNode nextNode { get; set; } 
     public int data { get; set; } 
     public MyLinkedListNode(int data) 
     { 
      this.data = data; 
     } 
     public MyLinkedListNode() 
     { 
      this.data = 0; 
     } 
    } 
    MyLinkedListNode headNode; 
    MyLinkedListNode prevNode; 
    MyLinkedListNode currentNode; 
    public LinkedList(int n, int min, int max) 
    { 
     length = n; 
     Random rand = new Random(); 
     headNode = new MyLinkedListNode(rand.Next(min, max)); 
     currentNode = headNode; 
     for (int i = 1; i < length; i++) 
     { 
      prevNode = currentNode; 
      currentNode.nextNode = new MyLinkedListNode(rand.Next(min, max)); 
      currentNode = currentNode.nextNode; 
     } 
     currentNode.nextNode = null; 
    } 
    public LinkedList() 
    { 
     headNode = new MyLinkedListNode(); 
     currentNode = headNode; 
    } 
    public override double Head() 
    { 
     currentNode = headNode; 
     prevNode = null; 
     return currentNode.data; 
    } 
    public override double Next() 
    { 
     prevNode = currentNode; 
     currentNode = currentNode.nextNode; 
     return currentNode.data; 
    } 
    public override void Swap(int a, int b) 
    { 
     prevNode.data = a; 
     currentNode.data = b; 
    } 

// mein Radixsort

public void radixSort() 
    { 
     int j = 0; 
     LinkedList tmp = new LinkedList(); 
     for (int shift = 31; shift > -1; --shift) 
     { 
      //I try to go trough old list 
      MyLinkedListNode current = headNode; 
      while (current != null) 
      { 
       bool move = (current.data << shift) >= 0; 
//I found this expression somewhere and I'm trying to use it to form a new Linked list (tmp) 
       if (shift == 0 ? !move : move) 
        ; 
       else 
       { 
        if (tmp.headNode == null) 
         tmp.headNode = currentNode; 
        else 
        { 
         tmp.currentNode.nextNode = current; 
//infinite loop happens on the commented line 
         //tmp.currentNode = tmp.currentNode.nextNode; 
         j++; 
        } 
       current = current.nextNode; 
       } 
      } 
    } 
} 

Answer 1

Nach dem C# Radixsort Beispiel müssen Sie ein Array von zehn Listen. Verschieben Sie die Knoten aus der ursprünglichen Liste in die zehn Listen, indem Sie einen Knoten mit der am wenigsten signifikanten Ziffer == '0' in array_of_lists [0], '1' in array_of_list [1] einfügen und so weiter. Nachdem die ursprüngliche Liste geleert wurde, verketten Sie das Listenfeld wieder in die ursprüngliche Liste und wiederholen Sie die Eingabe für die vorletzte Stelle. Wiederholen Sie den Vorgang, bis alle Ziffern bearbeitet sind.

Sie könnten eine größere Basis verwenden, z. B. Basis 16, wo Sie ein Array mit 16 Listen verwenden würden. Sie können dann jede "Ziffer" mit einer Schicht und einer and auswählen.