Ja. Ausgehend von der äußersten linken Position setzen wir das -Element dort in seine korrekte Position i, indem wir es mit dem (anderen) falsch platzierten Element an dieser Position austauschen. Hier benötigen wir den O (1) -Zusatzraum. Wir tauschen Paare von Elementen solange um, bis das Element in dieser Position korrekt ist. Nur dann gehen wir zur nächsten Position und machen dasselbe.
Beispiel:
[5 3 2 1 0 4] Anfangszustand
[4 3 2 1 0 5] getauscht (5,4), 5 ist jetzt in der richtigen Position, aber 4 ist immer noch falsch
[0 3 2 1 4 5] getauscht (4,0), jetzt sind sowohl 4 als auch 0 in den richtigen Positionen, gehe zur nächsten Position
[0 1 2 3 4 5] getauscht (3,1), jetzt sind 1 und 3 beide in der richtigen Position, gehen Sie weiter zur nächsten Position
[0 1 2 3 4 5] alle Elemente sind in den richtigen Positionen, Ende.
Hinweis :
Da jede swap-Operation mindestens eines (der zwei) Elemente in die richtige Position bringt, brauchen wir nicht mehr als N solche Swaps.
Zachs Lösung ist sehr gut.
Trotzdem habe ich mich gefragt, warum es nötig ist, zu sortieren. Wenn Sie die Permutation der Indizes haben, verwenden Sie die Werte als Zeiger auf das alte Array.
Dies kann die Notwendigkeit beseitigen, das Array an erster Stelle zu sortieren. Dies ist keine Lösung, die in allen Fällen verwendet werden kann, aber es wird in den meisten Fällen gut funktionieren.
Zum Beispiel:
%Vor%Wenn Sie jetzt die Werte in a durchsuchen möchten, können Sie etwas wie (Pseudocode) tun:
%Vor%Wenn Sie die Werte in der neuen Reihenfolge durchlaufen möchten, tun Sie Folgendes:
%Vor%Wie bereits erwähnt, kann diese Lösung in vielen Fällen ausreichend sein, in einigen anderen Fällen jedoch nicht. In anderen Fällen können Sie die Lösung von Zach.But für die Fälle verwenden, in denen diese Lösung verwendet werden kann, es ist besser, da überhaupt keine Sortierung erforderlich ist.
Tags und Links algorithm permutation vector swap