In Python sortieren. Lassen Sie uns als nächstes über den Algorithmus nachdenken.

Sortieren nach Methode, eingebaute Funktion

Betrachten Sie zunächst das Sortieren der folgenden Liste.

data = [5, 3, 2, 4, 1, 6]

Es gibt zwei Arten von sort () und sorted () zum Sortieren von Listentypen in aufsteigender oder absteigender Reihenfolge in Python. --List type method sort (): Sortiert die Liste selbst

• Eingebaute Funktion sortiert (): Gibt eine sortierte Liste als neuen Rückgabewert zurück

Listentyp Methode sort ()

Schreiben Sie die ursprüngliche Liste selbst neu.

data.sort()
print(data)
# [1, 2, 3, 4, 5, 6]

Die Standardeinstellung ist aufsteigende Sortierung. Setzen Sie das Argument umgekehrt auf True, um es in absteigender Reihenfolge zu sortieren.

data.sort(reverse = True)
print(data)
# [6, 5, 4, 3, 2, 1]

Beachten Sie, dass sort () None zurückgibt.

x = data.sort()
print(x)
# None

Eingebaute Funktion sortiert ()

Wenn Sie die Liste angeben, die Sie im Argument sortieren möchten, wird eine neue sortierte Liste generiert und als Rückgabewert zurückgegeben.

new_data1 = sorted(data)
print(new_data1)
# [1, 2, 3, 4, 5, 6]

Wie sort () ist sorted () standardmäßig in aufsteigender Reihenfolge. Setzen Sie das Argument umgekehrt auf True, um es in absteigender Reihenfolge zu sortieren.

new_data2 = sorted(data, reverse = True)
print(new_data2)
# [6, 5, 4, 3, 2, 1]

Sortieralgorithmus

Fassen wir die drei Sortieralgorithmen zusammen. Geschwindigkeit, Speichernutzung usw. sind mir egal, weil ich sie nur alle zusammen betrachte. Die Standardeinstellung ist aufsteigende Reihenfolge. Wenn Sie in Kommentar ändern, wird die Reihenfolge absteigend.

Denken Sortieralgorithmus

• Blasensortierung
• Sort einfügen --Zusammenführen, sortieren

Blasensorte

Es wird wiederholt, zwei benachbarte Werte zu vergleichen und nach den Bedingungen zu sortieren.

bubble_sort

for i in range(len(data)):
    for j in range(len(data) - 1):
        if data[j] > data[j+1]: # data[j] < data[j+1]
            data[j], data[j+1] = data[j+1], data[j]
print(data)
# [1, 2, 3, 4, 5, 6]

Sortierung einfügen

Platzieren Sie das Ziel an der entsprechenden Position für die ausgerichteten Daten. Diesmal wird die 2-Minuten-Suche nicht verwendet.

insert_sort

for i in range(1, len(data)):
    j = i - 1
    target = data[i]
    while data[j] > target and j >= 0: # data[j] < target
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = target
print(data)
# [1, 2, 3, 4, 5, 6]

Zusammenführen, sortieren

Teilen Sie die Liste in kleinere Einheiten, vergleichen Sie die Anfänge der beiden Listen und kombinieren Sie sie zu einer.

merge_sort

import math

def merge(x,y):
    m = []
    i = 0
    while i < len(x):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1
    i = 0
    while i < len(y):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1

    while x != [] and y != []:
        if x[0] < y[0]: # x[0] > y[0]
            m.append(x.pop(0))
        else:
            m.append(y.pop(0))
    if x == []:
        m += y
    else:
        m += x
    return m

data=[7,4,2,8,1,5,3,9,6]
n = 0
i = math.log2(len(data))
while n < i+1:
    tmp = []
    k=0
    while k < len(data):
        tmp = tmp
        m=merge(data[k:k+2**n],data[k+2**n:k+2**(n+1)])
        tmp += m
        k += 2**(n+1)
    data.clear()
    data += tmp
    n += n+1

print(data)
# [1, 2, 3, 4, 5, 6]

Am Ende

Da dies Qiitas erster Beitrag ist, denke ich, dass es viele Punkte gibt, die nicht erreicht werden können. Bitte weisen Sie darauf hin. Blasensortierungen und Einfügesortierungen waren relativ schnell, aber Zusammenführungssortierungen dauerten einige Zeit.