Stellen Sie sich vor, Sie haben ein Stück Papier in der Hand mit 1.000 aufgeführten Namen und müssen eine davon finden, aber diese Liste befindet sich nicht in alphabetischer Reihenfolge. Es w?re sehr frustrierend, nicht wahr? W?hrend es lange dauert, um diese Liste zu kl?ren, erleichtert es viel einfacher, Namen zu finden. Das Sortieren von Dingen ist also unser menschliches natürliches Verlangen, und die Suche nach sortierten Listen ist offensichtlich mehr arbeitssparend als die Suche nach ungeordneten Listen.

In der Computerwelt kann die Liste der Suchvorg?nge sehr gro? sein, und sogar schnelle Computer kann die Leistung beeintr?chtigt werden. In diesem Fall w?re ein geeigneter Sortier- und Suchalgorithmus die L?sung für solche Probleme. Sortieren ist der Prozess der Sortierung einer Liste von Werten in der Reihenfolge, w?hrend die Suche der Prozess des Findens der Werteposition in der Liste ist.

Um die Bedeutung dieser Ausgabe zu veranschaulichen, lassen Sie mich Ihnen zeigen, was der gro?e amerikanische Informatiker Donald Knuth sagte:

Computerhersteller in den 1960er Jahren sch?tzten, dass bei allen Kunden mehr als 25% ihrer Computerrunzleiter für die Sortierung aufgewendet wurden. In vielen Installationsf?llen nimmt die Sortieraufgabe mehr als die H?lfte der Berechnungszeit ein. Aus diesen Statistiken k?nnen wir schlie?en, dass (i) Sortierung viele wichtige Anwendungen hat oder (ii) viele Menschen sortieren, wenn sie nicht sollten oder (iii) ineffiziente Sortieralgorithmen weit verbreitet sind. —— "Die Kunst des Computerprogrammierens" Band 3: Sortieren und Suche, Seite 3

In diesem Tutorial werde ich Ihnen zeigen, wie Sie den Auswahl -Sortieralgorithmus und den linearen Suchalgorithmus implementieren.

Aber bevor wir anfangen, wenn Sie nur in Ihrem Python-Code sortieren und suchen m?chten, zeige ich Ihnen die integrierte Methode.

integrierte Sortiermethoden und Funktionen in Python

Sie k?nnen mit Python viele Sortieralgorithmen erstellen. Dies ist eine gute Lernübung, aber für Produktionsanwendungen sollten Sie sich an integrierte gespeicherte Funktionen und Methoden in Python halten.

Python hat eine list.sort() -Methode, mit der Sie die Liste an Ort und Stelle sortieren k?nnen. Der Sortieralgorithmus, der hinter den Kulissen von Python verwendet wird, hei?t Timsort. Es ist ein Hybridsortieralgorithmus, der auf Sortier- und Zusammenführungssortierungen basiert und in vielen Leben im realen Leben eine hervorragende Leistung bietet. Hier ist ein Beispiel für die Verwendung dieser beiden Funktionen und Methoden:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

Sie k?nnen einige Situationen im obigen Code bemerken. Die Funktion sorted() gibt eine neue sortierte Liste zurück, ohne die ursprüngliche Liste marks_a zu ?ndern. Die ursprüngliche Liste bleibt jedoch gleich. Wenn wir dagegen die marks_b -Methode auf sort() aufrufen, gibt es None zurück.

Sie k?nnen einige Parameter übergeben, um das Sortierverhalten zu ?ndern. übergeben Sie beispielsweise eine Funktion an den Parameter reverse, der unsere Liste der W?rter alphabetisch ohne Parameter sortiert. Im zweiten Fall verwenden wir sorted(), um die Reihenfolge sortierter W?rter umzukehren. reverse=True

W?hlen Sie Sortieralgorithmus

W?hlen Sie sortieren Der Algorithmus basiert auf einer kontinuierlichen Auswahl des Minimal- oder Maximalwerts. Angenommen, wir haben eine Liste, die wir in aufsteigender Reihenfolge sortieren m?chten (klein bis gro?). Das kleinste Element befindet sich am Anfang der Liste und das gr??te Element befindet sich am Ende der Liste.

Angenommen, die ursprüngliche Liste sieht folgenderma?en aus:

| 7 | 5 | 3.5 | 4 | 3.1 |

Das erste, was wir tun müssen, ist, den Wert

minimal in der Liste in diesem Fall zu finden. 3.1

Wenn der Mindestwert gefunden wird, tauschen Sie den Mindestwert mit dem ersten Element in der Liste

aus. Das hei?t, wechseln Sie mit aus. Die Liste sieht jetzt so aus: 3.1 7

| 3.1 | 5 | 3.5 | 4 | 7 | Jetzt, da wir die richtige Position des ersten Elements in der Liste bestimmen, wiederholen wir die obigen Schritte (finden Sie den Mindestwert) aus dem zweiten

-Element der Liste. Wir k?nnen feststellen, dass der Mindestwert in der Liste (ab dem zweiten Element)

betr?gt. Also werden wir jetzt mit austauschen. Die Liste wird jetzt: 3.5 3.5 5

Zu diesem Zeitpunkt stellen wir sicher, dass das erste Element und das zweite Element in ihrer richtigen Position sind. | 3.1 | 3.5 | 5 | 4 | 7 |

Jetzt überprüfen wir den Mindestwert im Rest der Liste, d. H. Beginnend mit dem dritten Element

. Der Mindestwert im Rest der Liste ist

, den wir jetzt mit

tauschen. Daher wird die Liste: 5 4 5

Daher bestimmen wir nun, dass die ersten drei | 3.1 | 3.5 | 4 | 5 | 7 | Elemente in der richtigen Position sind und der Prozess auf diese Weise fortgesetzt wird.

Lassen Sie uns sehen, wie der Auswahl -Sortieralgorithmus in Python (basierend auf Isai Damier) implementiert wird:

Testen wir den Algorithmus, indem Sie die folgende Anweisung am Ende des obigen Skripts hinzufügen:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

In diesem Fall sollten Sie die folgende Ausgabe erhalten:

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

linearer Suchalgorithmus

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Linearsuche

Algorithmus ist ein einfacher Algorithmus, bei dem jedes Element in der Liste überprüft wird (ab dem ersten Element), bis das gewünschte Element gefunden oder das Ende der Liste erreicht ist.

Der lineare Suchalgorithmus wird wie folgt in Python implementiert (basierend auf der Python -Schule):

testen wir den Code. Geben Sie die folgende Anweisung am Ende des obigen Python -Skripts ein:

Stellen Sie bei der Eingabe von

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

sicher, dass es zwischen einzelnen oder doppelten Zitaten liegt (d. H.

). Wenn Sie beispielsweise

eingeben, sollten Sie die folgende Ausgabe erhalten:

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

input 'pencil' 'pencil' und wenn Sie

als Eingabe eingeben, erhalten Sie die folgende Ausgabe:

Oops, your item seems not to be in the bag

Schlussfolgerung

Wie wir gesehen haben, erweist sich Python wieder als Programmiersprache, die das Konzept der Algorithmen leicht programmieren kann, genau wie wir es mit Sortier- und Suchalgorithmen hier zu tun haben.

Es ist zu beachten, dass es andere Arten der Sortier- und Suchalgorithmen gibt. Wenn Sie mit Python tiefer in diese Algorithmen eintauchen m?chten, k?nnen Sie sich auf das kostenlose python-objektorientierte Programmierlehrbuch beziehen.

Das obige ist der detaillierte Inhalt vonSortieren und Suche in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!