Einfache Auswahlsortierung: (Wählen Sie den kleinsten Wert aus, setzen Sie ihn an die erste Stelle und verschieben Sie dann den ersten Wert nach hinten usw.) Vergleichen Sie den ersten Wert nacheinander mit jedem weiteren und setzen Sie jeweils den kleinsten Wert an die Spitze Die Bits werden nach hinten verschoben (d. h. das erste gerade ausgewählte Bit ist der Mindestwert und wird nicht mehr in den Vergleich einbezogen, und die Anzahl der Vergleiche wird um 1 reduziert)
Komplexität: Die Anzahl der Die zum Verschieben des Datensatzes erforderlichen Operationen betragen weniger als 0–3 (n-1). Unabhängig von der anfänglichen Anordnung der Datensätze ist die Anzahl der erforderlichen Vergleiche zwischen Schlüsselwörtern gleich, nämlich n(n-1)/2, und die Gesamtzeitkomplexität ist O(n2);
Raumkomplexität O(1)
Algorithmusverbesserung: Bei jedem Vergleich wird der kleinste Wert zuerst gesetzt, damit Sie ihn bis zum Ende vergleichen und den kleinsten finden können Wert, und setzen Sie ihn direkt an die erste Stelle. Eliminieren Sie bedeutungslose Tausch- und Verschiebungsvorgänge. Sie können auch die Richtung ändern und das letzte Bit mit jedem vorherigen vergleichen, sodass der Maximalwert jedes Mal nach unten sinkt und das letzte Bit vorwärts geht.
JAVA-Quellcode:
public static void selectSort(Date[] days) {
int min;
Date temp;
for (int i = 0; i < days.length; i++) {
min = i;
for (int j = min + 1; j < days.length; j++) {
if (days[min].compare(days[j]) > 0) {
min = j;
}
}
if (min != i) {
temp = days[i];
days[i] = days[min];
days[min] = temp;
}
}
}
class Date {
int year, month, day;
Date(int y, int m, int d) {
year = y;
month = m;
day = d;
}
public int compare(Date date) {
return year > date.year ? 1 : year < date.year ? -1
: month > date.month ? 1 : month < date.month ? -1
: day > date.day ? 1 : day < date.day ? -1 : 0;
}
public void print() {
System.out.println(year + " " + month + " " + day);
}
} Einfache Auswahlsortierung:
Die einfache Auswahlsortierung ähnelt der Blasensortierung und funktioniert jedes Mal. Wählen Sie den höchsten Wert aus den verbleibenden aus Elementsatz und füllen Sie ihn an der aktuellen Position. Der einzige Unterschied besteht darin, dass die Blasensortierung die Position des Elements jedes Mal austauscht, wenn sie feststellt, dass sie kleiner (oder größer) als der aktuelle Wert ist, während die einfache Auswahlsortierung den höchsten Wert unter den verbleibenden Elementen auswählt und Daten mit dem aktuellen austauscht Position.
Zum Beispiel für die Elementmenge R={37, 40, 38, 42, 461, 5, 7, 9, 12}
Im ersten Sortierdurchlauf wird 37 direkt ausgetauscht mit 5, Bilden Sie eine neue Sequenz R1={5,40,38,42,461,37,7,9,12}
Bei der zweiten Sortierung: 40 wird direkt mit 7 ausgetauscht, um eine neue Sequenz R2={5, 7, 38,42,461,37,40,9,12}
und so weiter bis zum letzten Element (Hinweis: Im zweiten Sortierdurchgang ist 38 kleiner als 42, aber es werden keine Daten ausgetauscht) .
Das Folgende ist eine Java-Implementierungsversion der einfachen Auswahlsortierung:
public static void selectionSort（int[] data） {
if （data == null || data.length <= 1）
return;
int i, j, value, minPos, len = data.length;
int outer = len - 1, tmp;
for （i = 0; i < outer; i++） {
value = data[i];
minPos = -1;
for （j = i + 1; j < len; j++） {
if （data[j] < value） {
minPos = j;
value = data[j];
}
}
if （minPos != -1） {
tmp = data[i];
data[i] = value;
data[minPos] = tmp;
}
// for （int k = 0; k < len; k++） {
// System.out.print（data[k] + " , "）；
// }
// System.out.println（）；
}
}
public static void main（String[] args） {
int[] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
selectionSort（coll）；
for （int i = 0; i < coll.length; i++） {
System.out.print（coll[i] + " , "）；
}
} Baumauswahlsortierung (Baumauswahlsortierung)
Der Baumauswahlsortierungsalgorithmus ist im Vergleich zur einfachen Auswahlsortierung typisch Algorithmus zum Austausch von Raum gegen Zeit. Die Idee besteht darin, 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 noch ein Element vorhanden ist. Konstruiert in einen vollständigen Binärbaum.
Beim Sortieren ist das Element das kleinste. Nehmen Sie das kleinste Element heraus, ersetzen Sie das Element durch den „Maximalwert“ und passen Sie dann den gesamten Binärbaum an.
Das Folgende ist eine Java-Implementierung der Baumauswahlsortierung:
public static void treeSelectionSort（int[] data） {
if （data == null || data.length <= 1）
return;
int len = data.length , low = 0 , i , j;
// add Auxiliary Space
int[] tmp = new int[2*len -1];
int tSize = tmp.length;
//construct a tree
for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{
tmp[j]=data[i];
}
for（i = tSize -1 ; i > 0 ; i-=2）{
tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
}
//end
//remove the minimum node.
while（low < len）{
data[low++] = tmp[0];
for（j=tSize-1;tmp[j]!=tmp[0];j--）；
tmp[j] = Integer.MAX_VALUE;
while（j > 0）{
if（j%2 == 0）{ //如果是右节点
tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = （j-1）/2;
}else{ //如果是左节点
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
}
} Beim Aufbau eines vollständigen Binärbaums benötigt ein Satz von N Elementen 2*N -1 Hilfsraum.
Code:
while（j > 0）{
if（j%2 == 0）{ //如果是右节点
tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = （j-1）/2;
}else{ //如果是左节点
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}implementiert die rekursive Konstruktion des Mindestwerts im neuen Satz.
Weitere Artikel zum Prinzip und zur Implementierung des einfachen JAVA-Auswahlsortieralgorithmus finden Sie auf der chinesischen PHP-Website!
