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.

Inhaltsverzeichnis

1. Einführung
2. Was ist ein Auswahlsortierungsalgorithmus?
3. Wie funktioniert die Auswahlsortierung?
   • Zeitkomplexit?t
   • Weltraumkomplexit?t
4. Implementierung in JavaScript
5. LeetCode-Probleme l?sen
6. Fazit

Einführung

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.

Was ist ein Auswahlsortierungsalgorithmus?

Der Auswahlsortierungsalgorithmus ist ein Sortieralgorithmus für den direkten Vergleich. Es unterteilt die Eingabeliste in zwei Teile:

1. Der sortierte Teil am linken Ende
2. Der unsortierte Teil am rechten Ende

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.

Wie funktioniert die Auswahlsortierung?

Lassen Sie uns ein Beispiel mit dem Array [64, 25, 12, 22, 11] durchgehen:

1. Anf?ngliches Array: [64, 25, 12, 22, 11]

• Sortierte Portion: []
• Unsortierter Anteil: [64, 25, 12, 22, 11]

1. Erster Durchgang:

• Minimum im unsortierten Teil finden: 11
• Tauschen Sie 11 mit dem ersten unsortierten Element (64)
• Ergebnis: [11, 25, 12, 22, 64]
• Sortierte Portion: [11]
• Unsortierter Anteil: [25, 12, 22, 64]

1. Zweiter Durchgang:

• Minimum im unsortierten Teil finden: 12
• Tauschen Sie 12 mit dem ersten unsortierten Element (25)
• Ergebnis: [11, 12, 25, 22, 64]
• Sortierte Portion: [11, 12]
• Unsortierter Anteil: [25, 22, 64]

1. Dritter Durchgang:

• Minimum im unsortierten Teil finden: 22
• Tauschen Sie 22 mit dem ersten unsortierten Element (25)
• Ergebnis: [11, 12, 22, 25, 64]
• Sortierte Portion: [11, 12, 22]
• Unsortierter Anteil: [25, 64]

1. Vierter Durchgang:

• Minimum in unsortierter Portion finden: 25
• 25 ist bereits in der richtigen Position
• Ergebnis: [11, 12, 22, 25, 64]
• Sortierte Portion: [11, 12, 22, 25]
• Unsortierter Anteil: [64]

1. Letzter Durchgang:
   • Nur ??noch ein Element übrig, es befindet sich automatisch an der richtigen Position
   • Endergebnis: [11, 12, 22, 25, 64]

Das Array ist jetzt vollst?ndig sortiert.

Zeitkomplexit?t

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:

• Die ?u?ere Schleife l?uft n-1 Mal
• Für jede Iteration der ?u?eren Schleife wird die innere Schleife n-i-1 Mal ausgeführt (wobei i die aktuelle Iteration der ?u?eren Schleife ist)

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.

Weltraumkomplexit?t

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.

Implementierung in JavaScript

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:

1. Wir definieren eine Funktion ?selectionSort“, die ein Array als Eingabe verwendet.
2. Wir durchlaufen das Array mit der ?u?eren Schleife (i), die die Grenze zwischen den sortierten und unsortierten Teilen darstellt.
3. Für jede Iteration gehen wir davon aus, dass das erste unsortierte Element das Minimum ist, und speichern seinen Index.
4. Wir verwenden dann eine innere Schleife (j), um das tats?chliche minimale Element im unsortierten Teil zu finden.
5. Wenn wir ein kleineres Element finden, aktualisieren wir minIndex.
6. Nachdem wir das Minimum gefunden haben, tauschen wir es bei Bedarf mit dem ersten unsortierten Element aus.
7. Wir wiederholen diesen Vorgang, bis das gesamte Array sortiert ist.

LeetCode-Probleme l?sen

L?sen wir ein Problem mit dem Leetcode-Algorithmus mithilfe des Auswahlsortierungsalgorithmus. Sollen wir?

Problem: Ein Array sortieren [Mittel]

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.

Abschluss

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.

Bleiben Sie auf dem Laufenden und verbunden

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:

Die gro?artige L?sung?Folgen

Softwareentwickler | Technischer Redakteur | Backend-, Web- und Mobilentwickler? | Leidenschaft für die Entwicklung effizienter und skalierbarer Softwarel?sungen. #letsconnect ?

• GitHub
• Linkedin
• X (Twitter)

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!