Sortieralgorithmus Man kann sagen, dass jeder Programmierer es beherrschen muss Es ist notwendig, deren Prinzipien und Implementierung zu verstehen Das Folgende ist eine Einführung in die Python-Implementierung der zehn am häufigsten verwendeten Sortieralgorithmen, um Ihnen das Lernen zu erleichtern.
01 Blasensortierung – Austauschsortierung 02 Schnellsortierung – Austauschsortierung
03 Auswahlsortierung – Auswahlsortierung 0 4 Heap-Sortierung – Auswahlsortierung
05 Einfügungssortierung - Einfügungssortierung
06 Hügelsortierung - Einfügungssortierung
07 Zusammenführungssortierung - Zusammenführungssortierung.
0 8 Zählsortierung – Verteilungssortierung
09 Radix-Sortierung – Verteilungssortierung
10 Eimersortierung – Verteilungssortierung
Benachbarte Elemente vergleichen. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.
Machen Sie dasselbe für jedes Paar benachbarter Elemente, beginnend mit dem ersten Paar am Anfang und endend mit dem letzten Paar am Ende. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.
Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.
Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind.
'''冒泡排序'''
def Bubble_Sort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Bubble_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]Legen Sie zunächst einen Teilwert fest und teilen Sie das Array durch diese Teilung in einen linken und einen rechten Teil Wert.
Konzentrieren Sie die Daten, die größer oder gleich dem Grenzwert sind, auf der rechten Seite des Arrays und die Daten, die kleiner als der Grenzwert sind, auf der linken Seite des Arrays. Zu diesem Zeitpunkt ist jedes Element im linken Teil kleiner oder gleich dem Teilwert und jedes Element im rechten Teil ist größer oder gleich dem Teilwert.
Dann können die Daten links und rechts unabhängig voneinander sortiert werden. Für die Array-Daten auf der linken Seite können Sie einen Teilerwert nehmen und diesen Teil der Daten in einen linken und einen rechten Teil aufteilen. Platzieren Sie auf ähnliche Weise den kleineren Wert auf der linken Seite und den größeren Wert auf der rechten Seite. Auch die Array-Daten rechts können auf ähnliche Weise verarbeitet werden.
Wiederholen Sie den obigen Vorgang, bis die Datensortierung der linken und rechten Teile abgeschlossen ist.
'''快速排序'''
def Quick_Sort(arr):
# 递归入口及出口
if len(arr) >= 2:
# 选取基准值，也可以选取第一个或最后一个元素
mid = arr[len(arr) // 2]
# 定义基准值左右两侧的列表
left, right = [], []
# 从原始数组中移除基准值
arr.remove(mid)
for num in arr:
if num >= mid:
right.append(num)
else:
left.append(num)
return Quick_Sort(left) + [mid] + Quick_Sort(right)
else:
return arr
arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]Finden Sie das kleinste (große) Element in der unsortierten Reihenfolge und speichern Sie es unter die Startposition der sortierten Sequenz.
Suchen Sie weiterhin das kleinste (große) Element aus den verbleibenden unsortierten Elementen und fügen Sie es dann am Ende der sortierten Sequenz ein.
und so weiter, bis alle Elemente sortiert sind.
'''选择排序'''
def Selection_Sort(arr):
for i in range(len(arr) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
'''插入排序'''
def Insertion_Sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Insertion_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
'''堆排序'''
def Heapify(arr, n, i):
largest = i
# 左右节点分块
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
# 大小值交换
arr[i], arr[largest] = arr[largest], arr[i]
# 递归
Heapify(arr, n, largest)
def Heap_Sort(arr):
nlen = len(arr)
for i in range(nlen, -1, -1):
# 调整节点
Heapify(arr, nlen, i)
for i in range(nlen - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
# 调整节点
Heapify(arr, i, 0)
return arr
arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75]
result = Heap_Sort(arr)
print('result list: ', result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]Das obige ist der detaillierte Inhalt vonDie zehn wichtigsten Sortieralgorithmen, die Programmierer beherrschen müssen (Teil 1). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
