Die zehn wichtigsten Sortieralgorithmen, die Programmierer beherrschen müssen (Teil 1)

Einführung in diese Ausgabe

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

01

Bubble Sort

Bubble Sort: Ein klassischer Sortieralgorithmus, denn während des Betriebs des Algorithmus werden die Extremwerte schrittweise angezeigt Pop-up wie Blasen am Grund des Wassers, daher der Name.

Algorithmusprinzip:

• 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.

Der Code lautet wie folgt:

'''冒泡排序'''
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]

02

Schnell Sortieren

Schnellsortierung: Teilen Sie die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile auf und sortieren Sie die beiden Teile der Daten dann schnell getrennt nach dieser Methode Der gesamte Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden, was eine Verbesserung gegenüber dem Blasensortierungsalgorithmus darstellt.

Algorithmusprinzip:

• 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.

Der Code lautet wie folgt:

'''快速排序'''
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]

03

Sortierung auswählen

.

Auswahlsortierung: Es handelt sich um eine einfache und intuitive Sortierung Algorithmus. Egal welche Daten eingegeben werden, die Zeitkomplexität beträgt O(n²). Bei der Verwendung gilt also: Je kleiner die Datengröße, desto besser.

Algorithmusprinzip:

• 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(&#39;result list: &#39;, result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

04

插入排序

插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序'''
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(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

05

堆排序

堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

算法原理：

• 创建一个堆 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(&#39;result list: &#39;, 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!