Auswahlsortierungskonzept
Auswahlsortierung ist ebenfalls ein Austauschsortierungsalgorithmus und weist eine gewisse Ähnlichkeit mit der Blasensortierung auf. Daher denke ich persönlich, dass die Auswahlsortierung als verbesserter Algorithmus der Blasensortierung angesehen werden kann. Die Idee ist folgende:
Angenommen, wir möchten jetzt das Array arr[] sortieren, das n Elemente hat.
1 Vergleichen Sie das erste Element (in Java ist der Index 0) und das zweite Element. Wenn das erstere größer als das letztere ist, darf es nicht das kleinste sein, aber wir sind nicht so besorgt wie der Blasensortierungsaustausch. Wir können eine temporäre Variable a festlegen, um den Index des aktuell kleinsten Elements zu speichern. Dann vergleichen wir weiterhin das aktuell kleinste Element mit dem dritten Element. Wenn es immer noch nicht das kleinste ist, ändern wir den Wert von a. Auf diese Weise können Sie bis zum Abschluss des Vergleichs mit dem letzten Element sicher sein, dass a den Index des kleinsten Elements speichert.
2. Wenn der Wert von a nicht 0 ist (Anfangswert, also der Index des ersten Elements), tauschen Sie die beiden Elemente mit den Indizes a und 0 aus.
3. Wiederholen Sie den obigen Vorgang, diesmal beginnend mit dem Element mit dem Index 1, da das kleinste Element bereits an der Position mit dem Index 0 platziert ist.
4. Tun Sie dies, bis nur noch das letzte Element übrig ist. Sie können sicher sein, dass dieses Element das größte ist.
5. Sortierung abgeschlossen.
Natürlich erfordert dieser Algorithmus auch n-1 Sortierrunden.
Es ist zu beachten, dass das Obige nur eine Methode ist, um jedes Mal den Mindestwert zu ermitteln. Tatsächlich können Sie auch jedes Mal den Maximalwert ermitteln, müssen ihn dann jedoch jedes Mal am Ende des Arrays platzieren.
Java-Implementierungscode:
SelectArray.java
package ch02; public class SelectArray { // 数组 private long[] arr; // 数组中有效数据的大小 private int elems; // 默认构造函数 public SelectArray() { arr = new long[50]; } public SelectArray(int max) { arr = new long[max]; } // 插入数据 public void insert(long value) { arr[elems] = value; elems++; } // 显示数据 public void display() { for (int i = 0; i < elems; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // 选择排序 public void selectSort(){ int min = 0; long tmp = 0L; for(int i = 0; i < elems -1; i++){ min = i; for(int j = i + 1; j < elems; j++) { if(arr[j] < arr[min]) { min = j; } } tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } }
Testcode:
package ch02; public class TestSelectArray { public static void main(String[] args) { SelectArray sArr = new SelectArray(); sArr.insert(89); sArr.insert(54); sArr.insert(667); sArr.insert(7); sArr.insert(12); sArr.insert(43); sArr.insert(12); sArr.display(); sArr.selectSort(); sArr.display(); } }
Ergebnis:
Weitere verwandte Artikel zur Java-Implementierung von Beispiel-Tutorials für Auswahlsortierungsalgorithmen finden Sie auf der chinesischen PHP-Website!