Unterschiedliche Sortierreihenfolgen - Teilen und Erobern?

  • Ich versuche, eine Liste von Objekten auf unterschiedliche Weise neu anzuordnen. Hier werde ich Ganzzahlen verwenden, könnte jedoch alles in dieser Liste sein.

    Der folgende Beispielcode sortiert 1,2,3,4,5,6,7,8 in das Folgende Reihenfolge: 1,8,2,7,3,6,4,5

    Also zuerst .. letzte .. zweite .. vorletzte etc .. es Vielleicht etwas klobig, aber es funktioniert.

    Jetzt versuche ich, die Liste in einer anderen Reihenfolge auszugeben, so dass sie sich immer in zwei Teile teilt. Ich denke, das kann Divide and Conquer heißen, aber nachdem ich versucht habe, rekursive Sortiercodes usw. anzusehen, bin ich mir nicht ganz klar, wie ich das hier implementieren soll.

    I ' m hofft, die Zahlen so zu ordnen.

    1,8,4,2,6,3,5,7

    erste, letzte, halbe, erste Hälfte, zweite Hälfte usw. ...

    In anderen Worten versuche ich also, die Menge der Zahlen aufzuteilen in hälfte ... dann für jede hälfte der Reihe nach halbieren .. und so weiter.

     1 2 3 4 5 6 7 8 
     1 (erster Punkt) 
     8 (letzter Posten) 
     4 (mittlerer Posten) 
     2 (Mitte der ersten Hälfte) 
     6 (Mitte der zweiten Hälfte) 
     3 (Mitte des ersten Blocks) 
     5 (Mitte 2. Teil) 
     7 (Mitte 3. Teil) 
     

    Wenn mir jemand zeigen könnte, wie das geht, mit diesem einfachen Beispiel, ' wäre wirklich großartig.

      static void Main(string[] args)
        {
    
            List<int> numberlist = new List<int>();
    
            numberlist.Add(1);
            numberlist.Add(2);
            numberlist.Add(3);
            numberlist.Add(4);
            numberlist.Add(5);
            numberlist.Add(6);
            numberlist.Add(7);
            numberlist.Add(8);
    
            int rev = numberlist.Count-1;
            int fwd = 0;
    
            // order 1,8,2,7,3,6,4,5
    
            for (int re = 0; re < numberlist.Count; re++)
            {
                if (re % 2 == 0)
                {
                    Console.WriteLine(numberlist[fwd]);
                    fwd++;                       
                }
                else
                {
                    Console.WriteLine(numberlist[rev]);
                    rev--;
                }
            }
            Console.ReadLine();
        }
     

    Weitere Beispielbereiche und Ausgabe, die von links nach rechts und von oben nach unten gelesen werden können:

     1 2 3 4 5 6 7 
     1 7 <4> | 2 5 
     3 6 
     
     1 2 3 4 5 6 7 8 9 10 11 12 | 1 12 | 6 | 3 9 | 2 4 7 10 
     5 8 11 
     
     
     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 1 16 | 8 | 4 12 
     2 6 10 14 
     3 5 7 9 11 13 15 
     
    22 November 2011
    outisBrayn
2 answers
  • Lassen Sie mich sehen, ob ich das Problem verstehe. Lassen Sie uns ein Beispiel mit mehr Elementen bearbeiten:

    Dies ist die gewünschte Reihenfolge?

     ABCDEFGHIJKLMNOPQ
    A               Q  
            I
        E       M
      C   G   K   O
     B D F H J L N P
     

    Das scheint einfach zu sein. Erstellen Sie eine Datenstruktur mit dem Namen "Interval", die zwei Felder enthält: die größte Untergrenze und die niedrigste Obergrenze. Das sind die Elemente, die die größte Sache sind, die unter dem Intervall liegt, und die kleinste Sache, die über dem Intervall liegt . Der Algorithmus sieht folgendermaßen aus:

     Input: the size of the array.
    Yield the first item -- if there is one
    Yield the last item -- if it is different from the first item.
    Make a queue of intervals.
    Enqueue the interval (0, array.Length - 1) 
    While the queue is not empty:
        Dequeue the queue to obtain the current item.
        Is the interval empty? If so, skip this interval
        Otherwise, the interval has a GLB, a LUB, and a value in the middle.
        Yield the middle of the interval
        Enqueue the interval (bottom, middle)
        Enqueue the interval (middle, top)
     

    Lassen Sie uns das obige Beispiel bearbeiten. Wir haben das Array ABCDEFGHIJKLMNOPQ.

     Yield A
    Yield Q
    Enqueue A-Q. The queue is now A-Q
    Is the queue empty? No.
    Dequeue the queue. It is now empty.
    current is A-Q
    Is the current interval empty? no.
    The middle is I.
    Yield I.
    Enqueue A-I. The queue is now A-I.
    Enqueue I-Q. The queue is now A-I, I-Q.
    Is the queue empty? No.
    Dequeue the queue. It is now I-Q.
    current is A-I.
    Is the current interval empty? No.
    The middle is E.
    Yield E.
    Enqueue A-E. The queue is now I-Q, A-E.
    Enqueue E-I. The queue is now I-Q, A-E, E-I
    Is the queue empty? No.
    Dequeue. The queue is now A-E, E-I
    current is I-Q
    The middle is M
    Yield M.
    Enqueue I-M
    Enqueue M-Q.  The queue is now A-E, E-I, I-M, M-Q
    OK, let's start skipping some steps here. The state of the queue and the yields are:
    Yield C
    E-I, I-M, M-Q, A-C, C-E
    Yield G
    I-M, M-Q, A-C, C-E, E-G, G-I
    Yield K
    M-Q, A-C, C-E, E-G, G-I, I-K, K-M
    yield O
    A-C, C-E, E-G, G-I, I-K, K-M, M-O, O-Q
    yield B
    C-E, E-G, G-I, I-K, K-M, M-O, O-Q, A-B, B-C
    OK, skip more steps...
    Yield D, F, H, J, L, N, P
    Queue is now A-B, B-C, C-D, D-E, ... P-Q
    Every interval is now empty, so we skip all of htem and we are done.
     

    Sinn ergeben?

    Der Trick hier ist zu Beachten Sie, dass es sich bei der gewünschten Reihenfolge um einen Breitenbesuch eines Baums handelt. Sie müssen nur in der Lage sein, das Array durch die Baumstruktur zu "durchschauen", die Sie durchqueren möchten.

    Die Reihenfolge erscheint übrigens etwas seltsam. Die Reihenfolge scheint größtenteils zu sein "den Bereich in zwei Teile teilen und zuerst die Mitte jedes Bereichs ergeben". Warum werden dann die beiden Extreme zuerst und nicht last ? Ich würde die Reihenfolge finden:

     ABCDEFGHIJKLMNOPQ
            I
        E       M
      C   G   K   O
     B D F H J L N P
    A               Q  
     

    intuitiver naheliegend; Wenn die Dinge "in der Mitte" immer Vorrang vor den "Extremen" haben, sollten die Extremen als letzte und nicht als Erste gelten.

    22 November 2011
    Eric Lippert
  • Ich kann eine ähnliche Auswahl zeigen. es ergibt sich eine etwas andere Reihenfolge als Ihre.

    Nehmen Sie die Zahlen von 0 bis 7 und drücken Sie sie binär aus: 000 001 010 011 100 101 110 111.

    Nun kehren Sie sie um: 000 100 010 110 001 101 011 111.

    Im Dezimalwert ergibt dies 0 4 2 6 1 3 5 7. Sie beginnen also mit dem ersten Element und dann zur Hälfte der Rest der Elemente, dann ein Viertel und drei Viertel, und schließlich alle ungeradzahligen Elemente.

    Offensichtlich funktioniert dieses Verfahren nur für genaue Zweierpotenzen.

    22 November 2011
    Neil