Einige Sorten werden in "Algorithm Introduction 3rd Edition (Band 1)" vorgestellt. Basierend auf diesem Pseudocode
Ist in Python implementiert. Gehen Sie genauso vor wie beim Pseudocode, um die Namen der Variablen nachzuahmen. Das an die unten beschriebene Sortierfunktion übergebene Argument "A" ist eine Liste, in der die Elemente in zufälliger Reihenfolge angeordnet sind.
Die Einfügesortierung kann wie folgt geschrieben werden:
insertion_sort.py
def insertion_sort(A):
for j in range(1, len(A)):
key = A[j]
i = j - 1
while i >= 0 and A[i] > key:
A[i + 1] = A[i]
i -= 1
A[i + 1] = key
return A
Die Zusammenführungssortierung besteht aus zwei Teilen.
--MERGE: Kombiniere zwei ausgerichtete Sequenzen zu einem ausgerichteten Array --MERGE-SORT: MERGE die unterteilten Sequenzen in der Reihenfolge durch rekursiven Aufruf
merge_sort.py
def merge(A, p, q, r):
n_1 = q - p + 1
n_2 = r - q
L = []
R = []
for i in range(n_1):
L.append(A[p + i])
for j in range(n_2):
R.append(A[q + j + 1])
L.append(SENTINEL)
R.append(SENTINEL)
i, j = 0, 0
for k in range(p, r + 1):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
return A
def merge_sort(A, p=0, r=None):
r = len(A) - 1 if r == None else r
if p < r:
q = (p + r) // 2
merge_sort(A, p, q)
merge_sort(A, q + 1, r)
merge(A, p, q, r)
return A
Die Heap-Sortierung verwendet eine Struktur namens Heap.
Erstellen Sie zunächst als vorläufige Vorbereitung eine Heap-Klasse, um den Heap in Python darzustellen.
Dies ist Pythons eingebautes Objekt list mit dem Attribut heap_size.
heap_sort.py
class Heap(list):
def __init__(self, *args):
super().__init__(*args)
self.heap_size = len(self)
Dieser Heap behält seine Funktion als Liste. Versuchen Sie zu schreiben:
heap = Heap([1, 2, 3, 2, 3, 4])
print("heap:", heap)
print("heap.heap_size:", heap.heap_size)
print("len(heap):", len(heap))
Das Ergebnis der Ausführung ist wie folgt:
heap: [1, 2, 3, 2, 3, 4]
heap.heap_size: 6
len(heap): 6
Die Heap-Sortierung kann mit 5 Teilen erfolgen.
--LEFT: Wenn der Heap durch einen Zweiviertelbaum dargestellt wird, gibt er das Element zurück, das das linke untergeordnete Element mit sich selbst als übergeordnetem Element ist.
Unter Verwendung der in der Vorbereitung erstellten Heap-Klasse lauten diese wie folgt:
heap_sort.py
def left(i):
return 2 * (i + 1) - 1
def right(i):
return 2 * (i + 1)
def max_heapify(A, i):
l = left(i)
r = right(i)
if l <= A.heap_size - 1 and A[l] > A[i]:
largest = l
else:
largest = i
if r <= A.heap_size - 1 and A[r] > A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, largest)
def build_max_heap(list_A):
A = Heap(list_A)
A.heap_size = len(A)
for i in reversed(range((len(A) - 1) // 2 + 1)):
max_heapify(A, i)
return A
def heap_sort(list_A):
A = build_max_heap(list_A) #Wobei A eine Instanz der Heap-Klasse wird
for i in reversed(range(1, len(A))):
A[0], A[i] = A[i], A[0]
A.heap_size = A.heap_size - 1
max_heapify(A, 0)
return A
Die schnelle Sortierung kann aus zwei Teilen erfolgen.
--PARTITION: $ A [p..r] $ besteht nur aus Elementen unterhalb des Pivots $ A [p..q-1] $ und $ A [q + 1 .. besteht nur aus Elementen, die größer als der Pivot sind Teilen Sie in zwei r] $ --QUICK-SORT: Rufen Sie PARTITION rekursiv auf, um das gesamte $ A [p..r] $ zu sortieren
Der Drehpunkt ist $ A [r] $, dh das Element ganz rechts.
quick_sort.py
def partition(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r):
if A[j] <= x:
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1
def quick_sort(A, p=0, r=None):
r = len(A) - 1 if r == None else r
if p < r:
q = partition(A, p, r)
quick_sort(A, p, q - 1)
quick_sort(A, q + 1, r)
return A
Alle vier Arten, die bisher erstellt wurden, sind die kleinsten links und die, die in der Reihenfolge nach rechts zunehmen. Erstellen Sie als Bonus vier Arten von Sorten in umgekehrter Reihenfolge. Der Name der Funktion ist so etwas wie "(Sortiername) _nicht erhöht".
Eine kurze Erklärung wird hinzugefügt, indem der Teil auskommentiert wird, der aus der ursprünglichen Sortierfunktion neu geschrieben wurde.
insertion_sort_nonincreasing.py
def insertion_sort_nonincreasing(A):
for j in range(1, len(A)):
key = A[j]
i = j - 1
while i >= 0 and A[i] < key: #Und und anschließende Ungleichheitsumleitung
A[i + 1] = A[i]
i -= 1
A[i + 1] = key
return A
merge_sort_nonincreasing.py
SENTINEL_SMALL = - float('inf') #Machen Sie die Wache minus unendlich
def merge_nonincreasing(A, p, q, r):
n_1 = q - p + 1
n_2 = r - q
L = []
R = []
for i in range(n_1):
L.append(A[p + i])
for j in range(n_2):
R.append(A[q + j + 1])
L.append(SENTINEL_SMALL) #Verwenden Sie einen Minus-Unendlichkeitsschutz
R.append(SENTINEL_SMALL) #Das gleiche wie oben
i, j = 0, 0
for k in range(p, r + 1):
if L[i] >= R[j]: #Neuorientierung der Ungleichheit
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
return A
def mergeSort_nonincreasing(A, p=0, r=None):
r = len(A) - 1 if r == None else r
if p < r:
q = (p + r) // 2
mergeSort_nonincreasing(A, p, q) #Benennen Sie sich um
mergeSort_nonincreasing(A, q + 1, r) #Das gleiche wie oben
merge_nonincreasing(A, p, q, r) #In nicht aufsteigender Reihenfolge zusammenführen
return A
heqp_sort_nonincreasing.py
def min_heapify(A, i): #Name min_mach es häufen
l = left(i)
r = right(i)
if l <= A.heap_size - 1 and A[l] < A[i]: #Und und anschließende Ungleichheitsumleitung
smallest = l #Wechseln Sie zum kleinsten statt zum größten
else:
smallest = i
if r <= A.heap_size - 1 and A[r] < A[smallest]: #Und und anschließende Ungleichheitsumleitung
smallest = r
if smallest != i:
A[i], A[smallest] = A[smallest], A[i]
min_heapify(A, smallest) # max_min statt zu häufen_heapify
def build_min_heap(list_A): #Build-Name_min_zu haufen
A = Heap(list_A)
A.heap_size = len(A)
for i in reversed(range((len(A) - 1) // 2 + 1)):
min_heapify(A, i) # max_min statt zu häufen_heapify
return A
def heapSort_nonincreasing(list_A):
A = build_min_heap(list_A) # build_max_bauen statt Haufen_min_heap
for i in reversed(range(1, len(A))):
A[0], A[i] = A[i], A[0]
A.heap_size = A.heap_size - 1
min_heapify(A, 0) # max_min statt zu häufen_heapify
return A
quick_sort_nonincreasing.py
def partition_nonincreasing(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r):
if A[j] >= x: #Neuorientierung der Ungleichheit
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1
def quickSort_nonincreasing(A, p=0, r=None):
r = len(A) - 1 if r == None else r
if p < r:
q = partition_nonincreasing(A, p, r) #Nennen Sie die nicht zunehmende Version
quickSort_nonincreasing(A, p, q - 1) #Das gleiche wie oben
quickSort_nonincreasing(A, q + 1, r) #Das gleiche wie oben
return A
Recommended Posts