Einfache Sortierung der Auswahl: (Wählen Sie den Mindestwert aus, setzen Sie ihn zuerst und dann bewegt sich das erste Bit rückwärts, also loop) Das erste Bit vergleicht mit jedem nach dem nächsten, jedes Mal, wenn das kleinste Bit gekrönt wird und das erste Bit rückwärts ist Fördern (dh die erste ausgewählte Ziffer ist der Mindestwert, der nicht mehr am Vergleich beteiligt ist. Die Anzahl der Vergleiche wird um 1 reduziert)
Komplexität: Die Anzahl der für die Durchführung der Datensatzbewegung erforderlichen Operationen beträgt 0--3 (N-1). / 2. Die Gesamtzeitkomplexität ist O (N2);
Raumkomplexität O (1)
Verbesserung der Algorithmus: Jedes Mal, wenn Sie vergleichen, ist es überhaupt den kleinsten Wert, damit Sie ihn mit dem Ende vergleichen, den Mindestwert finden und sie in erster Linie direkt einsetzen, um bedeutungslose Schalt- und Bewegungsvorgänge zu beseitigen. Sie können die Richtung auch ändern, das letzte Bit mit jedem vorherigen vergleichen und den Maximalwert jedes Mal nach unten bringen und das letzte Bit nach vorne drücken.
Java -Quellcode:
Die Codekopie lautet wie folgt:
public static void selectSort (Datum [] Tage) {
int min;
Datumstemperatur;
für (int i = 0; i <days.length; i ++) {
min = i;
für (int j = min+1; j <days.length; j ++) {
if (Tage [min] .Compare (Tage [j])> 0) {
min = j;
}
}
if (min! = i) {
temp = Tage [i];
Tage [i] = Tage [min];
Tage [min] = temp;
}
}
}
Klassendatum {
int Jahr, Monat, Tag;
Datum (int y, int m, int d) {
Jahr = y;
Monat = m;
Tag = D;
}
public int compare (Datum Datum) {
Rückgabejahr> Datum
: Monat> Datum.month?
: Tag> Datum.Day?
}
public void print () {
System.out.println (Jahr + "" + Monat + "" + Tag);
}
}
Einfache Sortierung der Auswahl:
Einfache Auswahlsortierung ähnelt der Blasensortierung (Blasensortierung). Der einzige Unterschied besteht darin, dass die Sortierung von Blasen die Position des Elements jedes Mal austauscht, wenn er feststellt Aktuelle Position.
Zum Beispiel für Elementset R = {37, 40, 38, 42, 461, 5, 7, 9, 12}
In erster Reihenfolge: 37 wird direkt mit 5 ausgetauscht und bildet eine neue Sequenz R1 = {5,40,38,42,461,37,7,9,12}
In der zweiten Ordnung: 40 wird direkt mit 7 ausgetauscht und bildet eine neue Sequenz R2 = {5,7,38,42,461,37,40,9,12}
Und so weiter bis zum letzten Element (Hinweis: In der zweiten Reihenfolge ist 38 kleiner als 42, aber sie tauschen keine Daten aus).
Hier ist eine Java -Implementierungsversion, die einfach sortiert wird:
Die Codekopie lautet wie folgt:
public static void selectionsSort (int [] data) {
if (data == null || data.length <= 1)
zurückkehren;
int i, j, Wert, Minpos, len = data.Length;
int out = len - 1, tmp;
für (i = 0; i <äußere; i ++) {
value = data [i];
Minpos = -1;
für (j = i+1; j <len; j ++) {
if (Daten [j] <Wert) {
Minpos = J;
value = data [j];
}
}
if (minpos! = -1) {
tmp = data [i];
Daten [i] = Wert;
Daten [Minpos] = TMP;
}
// für (int k = 0; k <len; k ++) {
// system.out.print (Daten [k] + ",");
//}
// system.out.println ();
}
}
public static void main (String [] args) {
int [] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
SelectionsOrt (Coll);
für (int i = 0; i <coll.length; i ++) {
System.out.print (Coll [i] + ",");
}
}
Sortierung der Baumauswahl
Der Sortieralgorithmus aus der Baumauswahl ist ein typischer Algorithmus, der im Vergleich zur einfachen Sortierung der Selektion Platz für die Zeit trifft. Die Idee ist, die sortierten N -Elemente zu behandeln, relativ kleine (n+1)/2 Zahlen zu konstruieren und dann relativ kleine [N+1]/4 Zahlen zu konstruieren, bis nur ein Element vorhanden ist. In einem völlig binären Baum gebaut.
Wenn Sie sortieren, ist das Element das kleinste.
Hier ist eine Java -Implementierungsversion der Sortierung der Baumauswahl:
Die Codekopie lautet wie folgt:
public static void treeselectionsSort (int [] data) {
if (data == null || data.length <= 1)
zurückkehren;
int len = data.length, low = 0, i, j;
// Hilfsraum hinzufügen
int [] tmp = new int [2*len -1];
int tSize = tmp.Length;
// einen Baum konstruieren
für (i = len-1, j = tmp.length-1; i> = 0; i-, j-) {
TMP [j] = Daten [i];
}
für (i = tSize -1; i> 0; i- = 2) {
TMP [(I-1)/2] = TMP [i]> TMP [I-1]?
}
//Ende
// den minimalen Knoten entfernen.
während (niedrig <len) {
Daten [niedrig ++] = TMP [0];
für (j = tsize-1; tmp [j]! = tmp [0]; j-);
TMP [j] = Integer.max_value;
while (j> 0) {
if (j%2 == 0) {// Wenn es sich um einen richtigen Knoten handelt
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
J = (j-1)/2;
} else {// Wenn es sich um den linken Knoten handelt
TMP [j/2] = TMP [j]> TMP [j+1]?
J = J/2;
}
}
}
}
Beim Bau eines vollständigen Binärbaums ist für eine Sammlung von N -Elementen 2*n -1 Hilfsraum erforderlich.
Code:
Die Codekopie lautet wie folgt:
while (j> 0) {
if (j%2 == 0) {// Wenn es sich um einen richtigen Knoten handelt
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
J = (j-1)/2;
} else {// Wenn es sich um den linken Knoten handelt
TMP [j/2] = TMP [j]> TMP [j+1]?
J = J/2;
}
}
Implementieren Sie dann eine rekursive Konstruktion des Mindestwerts im neuen Satz.