Wie behandelt Auswahlsortierung doppelte Werte in Arrays? Es fällt mir schwer, die Antwort online zu finden.Auswahl Sortierverhalten mit Duplikaten
Wenn ich ein Array wie [8, 4, 7, 3, 9, 3] habe, welchen Index wird die Sortierung auswählen, um mit dem ersten Durchlauf des Arrays zu tauschen?
Der 3. Index oder der 5. Index?
Obwohl Ihre spezifische Frage zum Austauschen in 3 leicht zu beantworten ist, ist eine allgemeinere Version davon nicht einfach, weil die Auswahl nicht stabil ist.
Klassische Implementierung wird zum Aufnehmen des nächsten Elements zu Swap ist
if (a[i] < a[iMin])
Sobald die erste 33 am dritten Index, da die Bedingung auswählen in Position 0, das zweite 3 bei Index fünf getauscht wird nicht ausgewählt sein.
Die Bedingung bedeutet, dass das früheste Duplikat gemäß der Anordnung vor dem aktuellen Durchgang des Algorithmus ausgewählt wird. Diese Anordnung ist jedoch möglicherweise nicht mit der ursprünglichen Anordnung der Elemente identisch.
Soweit Duplikate weiter unten im Auswahlprozess gehen, gibt es keine Garantie, da eine kleinere Zahl vor ihnen eingefügt werden kann.
Zum Beispiel wird in dieser anfänglichen Anordnung
[3, 3, 1]
die 3 bei Index Null wird zuletzt aufgenommen werden, da die erste Iteration wird es bis zum Ende des Arrays des ganzen Weg bewegen.
Es ist abhängig von der Implementierung. In der Regel beginnt eine Schleife jedoch von links nach rechts zu scannen und erhält die erste .
Aber wie ich sage, das ist kein Standard.
Dies ist eine mögliche Implementierung gemäß Wikipedia:
procedure SelectionSort(a: list to sorts);
for i = 1 to n - 1
posmin ← i
for j = (i + 1) to n
if a[j] < a[posmin]
posmin ← j
tmp ← a[i]
a[i] ← a[posmin]
a[posmin] ← tmp