So implementieren Sie acht Sortieralgorithmen in Python

Dieser Artikel stellt hauptsächlich die Python-Implementierung der acht Sortieralgorithmen vor und bietet eine detaillierte Beschreibung und Code-Implementierung der acht Sortieralgorithmen. Interessierte Freunde können sich auf die

Python-Implementierung der acht Sortieralgorithmen beziehen Inhalt wie folgt:

1. Einfügungssortierung
Beschreibung

Der grundlegende Vorgang der Einfügungssortierung besteht darin, Daten in die sortierten geordneten Daten einzufügen Erhalten Sie neue geordnete Daten mit der Zahl plus eins. Der Algorithmus eignet sich zum Sortieren einer kleinen Datenmenge und die zeitliche Komplexität beträgt O (n ^ 2). Es handelt sich um eine stabile Sortiermethode. Der Einfügealgorithmus teilt das zu sortierende Array in zwei Teile: Der erste Teil enthält alle Elemente des Arrays mit Ausnahme des letzten Elements (wodurch das Array um einen weiteren Platz für eine Einfügeposition erweitert wird), und der zweite Teil enthält nur dieses Element (d. h. das einzufügende Element). Nachdem der erste Teil sortiert ist, wird dieses letzte Element in den sortierten ersten Teil eingefügt.

Code-Implementierung

def insert_sort(lists):
  # 插入排序
  count = len(lists)
  for i in range(1, count):
    key = lists[i]
    j = i - 1
    while j >= 0:
      if lists[j] > key:
        lists[j + 1] = lists[j]
        lists[j] = key
      j -= 1
  return lists

2. Hill-Sortierung
Beschreibung

Shell Sortieren ist eine Art Einfügesortierung. Es wird auch als reduzierende inkrementelle Sortierung bezeichnet und ist eine effizientere und verbesserte Version des Sortieralgorithmus mit direkter Einfügung. Hill-Sortierung ist ein instabiler Sortieralgorithmus. Diese Methode ist DL zu verdanken. Shell wurde nach seinem Vorschlag im Jahr 1959 benannt. Die Hill-Sortierung gruppiert Datensätze nach einem bestimmten Inkrement und sortiert jede Gruppe mithilfe des Sortieralgorithmus für direkte Einfügung. Mit zunehmender Inkrementierung enthält jede Gruppe immer mehr Schlüsselwörter. Wenn die Inkrementierung auf 1 abnimmt, wurde die gesamte Datei gruppiert in genau eine Gruppe, und der Algorithmus terminiert.

Code-Implementierung

def shell_sort(lists):
  # 希尔排序
  count = len(lists)
  step = 2
  group = count / step
  while group > 0:
    for i in range(0, group):
      j = i + group
      while j < count:
        k = j - group
        key = lists[j]
        while k >= 0:
          if lists[k] > key:
            lists[k + group] = lists[k]
            lists[k] = key
          k -= group
        j += group
    group /= step
  return lists

3. Blasensortierung
Beschreibung

Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde.

Code-Implementierung

def bubble_sort(lists):
  # 冒泡排序
  count = len(lists)
  for i in range(0, count):
    for j in range(i + 1, count):
      if lists[i] > lists[j]:
        lists[i], lists[j] = lists[j], lists[i]
  return lists

4. Schnelle Sortierung
Beschreibung

Bestanden Die Sortierung in einem Durchgang unterteilt die zu sortierenden Daten in zwei unabhängige Teile. Alle Daten in einem Teil sind kleiner als alle Daten in dem anderen Teil. Anschließend werden die beiden Teile der Daten schnell getrennt sortiert Der Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Reihenfolge werden.

Code-Implementierung

def quick_sort(lists, left, right):
  # 快速排序
  if left >= right:
    return lists
  key = lists[left]
  low = left
  high = right
  while left < right:
    while left < right and lists[right] >= key:
      right -= 1
    lists[left] = lists[right]
    while left < right and lists[left] <= key:
      left += 1
    lists[right] = lists[left]
  lists[right] = key
  quick_sort(lists, low, left - 1)
  quick_sort(lists, left + 1, high)
  return lists

5. Direkte Auswahlsortierung
Beschreibung

Grundidee: Wählen Sie im ersten Durchgang den kleinsten Datensatz unter den zu sortierenden Datensätzen r1 ~ r[n] aus und tauschen Sie ihn gegen r1 aus. Wählen Sie im zweiten Durchgang den kleinsten Datensatz unter den zu sortierenden Datensätzen r2 ~ r[n] aus ] , tauschen Sie es mit r2; usw. aus, der i-te Durchgang wählt den kleinsten Datensatz unter den zu sortierenden Datensätzen r[i] ~ r[n] aus und tauscht ihn mit r[i] aus, sodass die geordnete Reihenfolge entsteht wächst weiter, bis alles sortiert ist.

Code-Implementierung

def select_sort(lists):
  # 选择排序
  count = len(lists)
  for i in range(0, count):
    min = i
    for j in range(i + 1, count):
      if lists[min] > lists[j]:
        min = j
    lists[min], lists[i] = lists[i], lists[min]
  return lists

6. Heap-Sortierung
Beschreibung

Heap Sortieren (Heapsort) bezieht sich auf einen Sortieralgorithmus, der eine Datenstruktur wie einen gestapelten Baum (Heap) verwendet. Es handelt sich um eine Art Auswahlsortierung. Sie können die Eigenschaften von Arrays nutzen, um das Element schnell an einem angegebenen Index zu finden. Der Heap ist in einen großen Root-Heap und einen kleinen Root-Heap unterteilt, bei denen es sich um einen vollständigen Binärbaum handelt. Die Anforderung eines großen Root-Heaps besteht darin, dass der Wert jedes Knotens nicht größer ist als der Wert seines übergeordneten Knotens, d. h. A[PARENT[i]] >= A[i]. Bei der nicht absteigenden Sortierung eines Arrays muss ein großer Root-Heap verwendet werden, da gemäß den Anforderungen eines großen Root-Heaps der Maximalwert oben im Heap liegen muss.

Code-Implementierung

# 调整堆
def adjust_heap(lists, i, size):
  lchild = 2 * i + 1
  rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)

# 创建堆
def build_heap(lists, size):
  for i in range(0, (size/2))[::-1]:
    adjust_heap(lists, i, size)

# 堆排序
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)

7. Zusammenführungssortierung
Beschreibung

Zusammenführung Sortieren ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung, die die Divide-and-Conquer-Methode (Pide and Conquer) verwendet. Führen Sie die bereits geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Ordnen Sie also zuerst jede Teilsequenz und dann die Teilsequenzsegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer bidirektionalen Zusammenführung.

Der Zusammenführungsprozess ist: Vergleichen Sie die Größen von a[i] und a[j], wenn a[i]≤a[j], kopieren Sie das Element a[i] in der ersten geordneten Liste nach r [k] und addiere 1 zu i bzw. k; andernfalls kopiere das Element a[j] in der zweiten geordneten Liste nach r[k] und addiere 1 zu j bzw. k. Dieser Zyklus wird fortgesetzt, bis eines der geordneten Listen werden abgerufen, und dann werden die verbleibenden Elemente in der anderen geordneten Liste in die Zellen in r vom Index k bis zum Index t kopiert. Normalerweise verwenden wir Rekursion, um den Zusammenführungssortierungsalgorithmus zu implementieren. Wir teilen zuerst das zu sortierende Intervall [s, t] in der Mitte, sortieren dann den linken Teilbereich, dann den rechten Teilbereich und verwenden schließlich a Zusammenführungsvorgang zwischen dem linken Intervall und dem rechten Intervall. In geordnete Intervalle [s,t] zusammenführen.

Code-Implementierung

def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  return result

def merge_sort(lists):
  # 归并排序
  if len(lists) <= 1:
    return lists
  num = len(lists) / 2
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

8. Radix-Sortierung
Beschreibung

Radix Die Sortierung (Radix-Sortierung) gehört zur „Verteilungssortierung“, auch bekannt als „Bucket-Sortierung“ oder „Bin-Sortierung“. Wie der Name schon sagt, verwendet sie einen Teil der Schlüsselwertinformationen, um die zu sortierenden Elemente in einigen „Buckets“ zu verteilen. Die Radix-Sortiermethode ist eine stabile Sortiermethode und ihre zeitliche Komplexität beträgt O (nlog(r)m), wobei r die genommene Basis und m die Anzahl der Heaps ist. Manchmal beträgt die Effizienz der Basis-Sortiermethode höher als andere Stabilitätssortiermethoden.

Code-Implementierung

import math
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      bucket[j/(radix**(i-1)) % (radix**i)].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
  return lists

以上就是Python实现八大排序算法的详细介绍，希望对大家的学习有所帮助。

Das obige ist der detaillierte Inhalt vonSo implementieren Sie acht Sortieralgorithmen in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!