Da wir über verschiedene Sortieralgorithmen gesprochen haben, lernen wir heute etwas über den Auswahlsortierungsalgorithmus. Ein Sortieralgorithmus, der die mögliche Mindestmenge an Auslagerungen in einer speicherbeschränkten Umgebung ermöglicht.
Auswahlsortierung ist ein einfacher, aber effektiver Sortieralgorithmus, der durch wiederholtes Auswählen des kleinsten (oder größten) Elements aus dem unsortierten Teil der Liste und Verschieben an den Anfang (oder Ende) des sortierten Teils funktioniert. Dieser Vorgang wird wiederholt, bis die gesamte Liste sortiert ist. In diesem Artikel werden wir uns mit den Details des Auswahlsortierungsalgorithmus, seiner Implementierung in JavaScript und seinen Anwendungen bei der Lösung realer Probleme befassen.
Der Auswahlsortierungsalgorithmus ist ein Sortieralgorithmus für den direkten Vergleich. Es unterteilt die Eingabeliste in zwei Teile:
Der Algorithmus wählt wiederholt das kleinste Element aus dem unsortierten Teil aus und tauscht es mit dem am weitesten links stehenden unsortierten Element aus, wodurch die Grenze zwischen dem sortierten und dem unsortierten Teil um ein Element nach rechts verschoben wird.
Lassen Sie uns ein Beispiel mit dem Array [64, 25, 12, 22, 11] durchgehen:
Das Array ist jetzt vollständig sortiert.
Selection Sort hat in allen Fällen (beste, durchschnittliche und schlechteste) eine zeitliche Komplexität von O(n^2), wobei n die Anzahl der Elemente im Array ist. Das liegt daran:
Dies führt zu ungefähr (n^2)/2 Vergleichen und n Swaps, was zu O(n^2) vereinfacht wird.
Aufgrund dieser quadratischen Zeitkomplexität ist die Auswahlsortierung für große Datensätze nicht effizient. Seine Einfachheit und die Tatsache, dass es die minimal mögliche Anzahl von Swaps durchführt, können es jedoch in bestimmten Situationen nützlich machen, insbesondere wenn der Hilfsspeicher begrenzt ist.
Selection Sort hat eine räumliche Komplexität von O(1), da es das Array direkt sortiert. Unabhängig von der Eingabegröße ist lediglich eine konstante Menge an zusätzlichem Speicherplatz erforderlich. Dies macht es speichereffizient, was in Umgebungen mit begrenztem Speicher von Vorteil sein kann.
Hier ist eine JavaScript-Implementierung des Auswahlsortierungsalgorithmus:
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
// Find the minimum element in the unsorted portion
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first unsorted element
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
Lassen Sie uns den Code aufschlüsseln:
Lösen wir ein Problem mit dem Leetcode-Algorithmus mithilfe des Auswahlsortierungsalgorithmus. Sollen wir?
Problem:Sortieren Sie bei einem gegebenen Array von Ganzzahlen das Array in aufsteigender Reihenfolge und geben Sie es zurück. Sie müssen das Problem ohne Verwendung integrierter Funktionen in O(nlog(n)) Zeitkomplexität und mit der geringstmöglichen räumlichen Komplexität lösen.
Ansatz:: Um dieses Problem zu lösen, können wir den Auswahlsortierungsalgorithmus direkt anwenden. Dies beinhaltet das Durchlaufen des Arrays, das Finden des kleinsten Elements im unsortierten Teil und den Austausch mit dem ersten unsortierten Element. Wir wiederholen diesen Vorgang, bis das gesamte Array sortiert ist.
Lösung:
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
// Find the minimum element in the unsorted portion
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first unsorted element
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
Diese Lösung wendet direkt den zuvor implementierten Auswahlsortierungsalgorithmus an. Obwohl das Problem dadurch korrekt gelöst wird, ist es erwähnenswert, dass diese Lösung aufgrund der O(n^2)-Zeitkomplexität der Auswahlsortierung möglicherweise das Zeitlimit für große Eingaben in LeetCode überschreitet. Das Bild unten zeigt, dass die Lösung richtig, aber nicht effizient ist.
Zusammenfassend lässt sich sagen, dass Selection Sort ein einfacher und intuitiver Sortieralgorithmus ist, der als hervorragender Einstieg in die Welt der Sortiertechniken dient. Aufgrund seiner Einfachheit ist es leicht zu verstehen und umzusetzen, was es zu einem wertvollen Lernwerkzeug für Anfänger macht. Aufgrund seiner quadratischen Zeitkomplexität O(n^2) ist es jedoch für große Datensätze nicht effizient. Für größere Datensätze oder leistungskritische Anwendungen werden effizientere Algorithmen wie QuickSort, MergeSort oder integrierte Sortierfunktionen bevorzugt.
Um sicherzustellen, dass Sie keinen Teil dieser Serie verpassen und um mit mir in Kontakt zu treten, um mehr darüber zu erfahren
Diskussionen über Softwareentwicklung (Web, Server, Mobil oder Scraping/Automatisierung), Daten
Strukturen und Algorithmen und andere spannende Technologiethemen, folgen Sie mir auf:
Bleiben Sie dran und viel Spaß beim Programmieren ???
Das obige ist der detaillierte Inhalt vonBeherrschen Sie den Sortieralgorithmus wie ein Profi. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
