A) Prinzip : Wählen Sie jedes Mal das kleinste Element aus den zu sortierenden Datensätzen aus und platzieren Sie es in der Reihenfolge am Ende der sortierten Sequenz, bis alle Datensätze sortiert sind. Das heißt, jede Reise wird in der geordneten Sequenz zwischen N-I+1 (i = 1, 2, ... n-1) als I-ter Datensatz ausgewählt. Die auf dieser Idee basierenden Algorithmen enthalten hauptsächlich eine einfache Sortierung der Auswahl, die Sortierung von Baumauswahl und die Sortierung von Haufen. (Dies ist nur eine häufige einfache Auswahlsortierung)
b) die grundlegende Idee der einfachen Auswahl der Sortierung : Angegeben ein Array: int [] arr = {n Daten darin}; Wählen Sie beim ersten Sortieren die kleinsten Daten in den Daten aus, die sortiert werden sollen [1] ~ arr [n] und tauschen Sie sie mit arr [1] aus; Wählen Sie beim zweiten Mal die kleinsten Daten in den Daten aus, die sortiert werden sollen [2] ~ arr [n], und tauschen Sie sie mit R [2] aus; Wählen Sie so weiter die kleinsten Daten in den Daten aus, die sortiert werden sollen [i] ~ arr [n], und tauschen Sie sie mit R [i] aus, bis alle Sortierungen abgeschlossen sind.
c) Beispiel : Array int [] arr = {5,2,8,4,9,1};
---------------------------------------------------
Erste Ordnung: Originaldaten: 528491
Mindestdaten 1, zuerst 1 setzen, dh 1 und 5 Austauschpositionen,
Sortieren Sie Ergebnis: 128495
---------------------------------------------------
Zweite Ordnung:
Die Daten außerhalb von 1 {28495} werden verglichen, 2 ist der kleinste,
Sortieren Sie Ergebnis: 128495
---------------------------------------------------
Die dritte Ordnung:
Andere Daten als 1 und 2 werden verglichen {8495}, 4 ist minimal, 8 und 4 werden ausgetauscht
Sortieren Sie Ergebnis: 124895
---------------------------------------------------
Die vierte Ordnung:
Andere Daten als 1, 2, 4 werden verglichen. {895}, 5 ist minimal, 8 und 5 werden ausgetauscht
Sortieren Sie Ergebnis: 124598
---------------------------------------------------
Die fünfte Ordnung:
Andere andere Daten als 1, 2, 4, 5 werden verglichen, 8 sind minimal, 8 und 9 werden ausgetauscht
Sortieren Sie Ergebnis: 124589
---------------------------------------------------
HINWEIS: Die Methode, um die kleinste Zahl in jeder Reihenfolge zu erhalten: Damit die Schleife verglichen werden kann, definieren Sie eine dritte variable Temperatur. Vergleichen Sie zuerst die ersten beiden Zahlen, geben Sie die kleinere Zahl in Temp und verwenden Sie dann Temp, um mit den verbleibenden Daten zu vergleichen. Wenn Daten kleiner als die Temperatur angezeigt werden, verwenden Sie sie anstelle der ursprünglichen Daten in Temp. Weitere Informationen finden Sie in Bezug auf die folgenden Codebeispiele, ich glaube, Sie haben die For -Loop -Erklärung gelernt, bevor Sie lernen, die Sortierung zu sortieren. Auf diese Weise wird es hier besonders leicht zu verstehen sein.
Codebeispiel:
// Sortieren Sie die öffentliche Klasse SelectionsSort {public static void main (String [] args) {int [] arr = {1,3,2,45,65,33,12}; System.out.println ("vor Exchange:"); für (int num: arr) {System.out.print (num+""); } // Wählen Sie die Optimierung der Sortierung für (int i = 0; i <arr.Length - 1; i ++) {// Sortieren Sie die I -Th -Reihenfolge int k = i; für (int j = k+1; j <arr.length; j ++) {// Wählen Sie den kleinsten Datensatz if (arr [j] <arr [k]) {k = j; // Beachten Sie den Standort des bisher gefundenen Mindestwerts}} // Nach dem Ende der inneren Schleife, dh nach der Ermittlung der Mindestnummer dieser Schleife, dann tauschen Sie dann aus (i! arr [i] = arr [k]; arr [k] = temp; }} System.out.println (); System.out.println ("After Swap:"); für (int num: arr) {System.out.print (num+""); }}}Screenshot des laufenden Ergebniss:
Wählen Sie die Zeitkomplexität der Sortierung aus: Die Anzahl der Vergleiche der einfachen Selektionssorten hat nichts mit der anfänglichen Sortierung der Sequenz zu tun. Unter der Annahme, dass die zu sortierte Sequenz N-Elemente hat, wird die Anzahl der Vergleiche immer n (n-1)/2 sein. Die Anzahl der Bewegungen hängt mit der anfänglichen Sortierung der Sequenz zusammen. Wenn die Sequenz positiv ist, ist die Anzahl der Bewegungen die geringste, was 0 ist. Wenn die Sequenz umgekehrt sequenziert ist, sind die meisten Bewegungen 3n (n-1)/2.
Zusammenfassend ist die zeitliche Komplexität der einfachen Sortierung O (N2).