Heim  >  Artikel  >  Backend-Entwicklung  >  Implementierungs- und Optimierungsleitfaden für die Python-Auswahlsortierung

Implementierungs- und Optimierungsleitfaden für die Python-Auswahlsortierung

WBOY
WBOYOriginal
2024-02-02 21:22:06712Durchsuche

Implementierungs- und Optimierungsleitfaden für die Python-Auswahlsortierung

Schritte und Optimierungsmethoden der Python-Auswahlsortierung

Selection Sort ist ein einfacher und intuitiver Sortieralgorithmus. Seine Grundidee besteht darin, jedes Mal das kleinste (oder größte) Element aus den zu sortierenden Datenelementen auszuwählen, es am Anfang der Sequenz zu speichern und dann weiterhin das kleinste (oder größte) Element aus den verbleibenden unsortierten Elementen zu finden. , am Ende der sortierten Sequenz platziert. Wiederholen Sie diesen Vorgang, bis alle zu sortierenden Datenelemente angeordnet sind.

Die Schritte der Auswahlsortierung können wie folgt zusammengefasst werden:

  1. Durchlaufen Sie die zu sortierende Sequenz und markieren Sie die aktuelle Position als Position des kleinsten Elements.
  2. Suchen Sie aus dem Element hinter der markierten Position ein Element, das kleiner als das aktuell kleinste Element ist, und aktualisieren Sie die markierte Position.
  3. Tauschen Sie das Element an der markierten Position mit dem Element an der minimalen Elementposition aus.
  4. Verwenden Sie das Element nach der markierten Position als neue Startposition und wiederholen Sie die Schritte 2 und 3.

Die Optimierungsmethoden der Auswahlsortierung sind:

  1. Finden Sie bei jedem Durchlauf gleichzeitig das minimale Element und das maximale Element und tauschen Sie sie gleichzeitig aus. Dadurch kann die Anzahl der Austausche reduziert und die Sortiereffizienz verbessert werden.
  2. Fügen Sie eine Beurteilung hinzu. Wenn während des Durchlaufvorgangs kein Austausch stattfindet, das heißt, die Sortierung abgeschlossen ist, wird der Sortiervorgang vorzeitig beendet.

Das Folgende ist ein Beispiel für einen Auswahlsortierungscode in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_pos = i
        max_pos = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_pos]:
                min_pos = j
            if arr[j] > arr[max_pos]:
                max_pos = j
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
        if max_pos == i:
            max_pos = min_pos
        if max_pos != n - 1 - i:
            arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i]
        if min_pos == n - 1 - i:
            min_pos = max_pos
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
    return arr

# 测试
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
sorted_arr = selection_sort(arr)
print("排序后:", sorted_arr)

Im obigen Code stimmt die Position der Variablen min_pos 记录最小元素的位置,使用变量 max_pos 记录最大元素的位置。在每次遍历中,通过比较更新这两个位置,然后进行交换。在列表长度为奇数时,如果 min_posmax_pos, die wir verwenden, zufällig mit der Startposition überein, und wir müssen die ausgetauschte Position überprüfen und verarbeiten.

Das Obige sind die Schritte und Optimierungsmethoden der Python-Auswahlsortierung sowie spezifische Codebeispiele. Obwohl die Auswahlsortierung einfach ist, ist sie weniger effizient und hat eine zeitliche Komplexität von O(n^2). Daher wird in praktischen Anwendungen bei großem Sortiermaßstab empfohlen, effizientere Sortieralgorithmen wie Schnellsortierung oder Zusammenführungssortierung zu verwenden.

Das obige ist der detaillierte Inhalt vonImplementierungs- und Optimierungsleitfaden für die Python-Auswahlsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn