Angenommen, ein Array ist gegeben durch a1, a2, ..., ak, _, a (k + 1), ..., an. Hier steht ein Unterstrich (_) für Leerzeichen. Wir können jedes Array-Element in diesen Raum verschieben. Wir können diese Operation beliebig oft wiederholen. Ist es möglich, jedes Array mit einem solchen Leerzeichen zu sortieren?Ist es möglich, ein Array mit einer temporären Variable/Platz zu sortieren?
Ja, es ist möglich.
Ein sortiertes Array ist nur eine bestimmte Permutation dieses Arrays.
Jede mögliche Permutation kann durch eine Abfolge einzelner Swaps erreicht werden.
Und ein Austausch kann mit einem einzigen temporären Element implementiert werden.
(Es ist tatsächlich möglich, ein Array von integrierten Typen ohne eine temporäre, XOR-Operationen zu verwenden).
Es gibt verschiedene Algorithmen für die In-Place-Sortierung. Der bemerkenswerteste ist die nicht-rekursive Version von quick-sort (da die rekursive Version Platz auf dem Stack belegen würde, der proportional zur Anzahl der rekursiven Aufrufe ist), was Ihnen im Durchschnitt O (n log n) Komplexität gibt.
Eine andere Möglichkeit ist die Verwendung weniger effizienter Algorithmen wie Insertion Sort und Bubble Sort, deren Kompliziertheit O (n^2) ist.
Für was Ihre spezifische Frage betrifft, das ist, diesen spezifischen Raum zu benutzen, können Sie es für das Tauschen verwenden, wie von Bathsheba gesagt, aber ich würde meine Zeit nicht verlieren, die diese Art von Operation tut.
Beachten Sie auch die Tatsache, dass, wenn Sie explizite Vorstellung von einem „ungenutzten Raum“ haben in der Mitte des Arrays, sollten Sie versuchen, ihre semantische zu verstehen, das heißt, was wäre die korrekte Platzierung in Bezug auf der Bestellung sein. Wenn Sie dies nicht tun, und Sie es dort belassen, wo es ist, würden Sie sich mit einer "kaputten" Invariante wiederfinden, und Sie werden Schwierigkeiten haben, Algorithmen wie die binäre Suche in Ihrer Sammlung zu implementieren.
Ich habe solche Container noch nicht im eigentlichen Code gesehen, aber der einfachste zu implementierende Algorithmus (nicht der effizienteste!) Ist es, mit dem ersten Element leer zu tauschen, dann den kleinsten mit leerem zuerst zu tauschen, dann nehme man an Der Container beginnt an der zweiten Position und wiederholt sich bis zur letzten Position, bei der es sich um den leeren Platz handelt. In diesem Fall bedeutet "Tauschen" nur, leere Fläche ausfüllen und andere Position als leer markieren.
Vielen Dank. Ich weiß sogar nicht, dass die ohne temporären Swap eine Version mit XOR haben. \t a = a^b; \t b = a^b; \t a = a^b; oder über Plus/Minus: \t a = a + b; \t b = a - b; \t a = a - b; –