Python implementiert acht Sortieralgorithmen

So implementieren Sie acht Sortieralgorithmen mit Python

1. Einfügungssortierung
Beschreibung
Einfügungssortierung Die grundlegende Operation besteht darin, ein Datenelement in die sortierten geordneten Daten einzufügen, wodurch neue geordnete Daten mit der Zahl plus eins erhalten werden. 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 Sort ist eine Art Einfügungssortierung. 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 tauscht sie aus, 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

Schnellsortierung
Beschreibung
Teilen Sie die zu sortierenden Daten durch einen Sortierdurchgang in zwei unabhängige Teile auf. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil und verwenden Sie dann diese Methode, um die beiden Teile der Daten schnell zu sortieren. Der gesamte Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz 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 🎜>
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 ihn aus r1 ; Im zweiten Durchgang wird der kleinste Datensatz aus den zu sortierenden Datensätzen r2 ~ r[n] ausgewählt und mit r2 usw. ausgetauscht. Im i-ten Durchgang wird der kleinste Datensatz ausgewählt Zu sortierende Datensätze r[i] ~ r[n] Holen Sie sich den kleinsten Datensatz und tauschen Sie ihn mit r[i] aus, sodass die geordnete Sequenz weiter wächst, bis alle sortiert sind.
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 >
Beschreibung Heapsort bezieht sich auf einen Sortieralgorithmus, der unter Verwendung einer Datenstruktur wie einem gestapelten Baum (Heap) entwickelt wurde. Es handelt sich um eine Art Auswahlsortierung. Mithilfe der Eigenschaften des Arrays können Sie das Element schnell am angegebenen Index 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

7、归并排序
描述 
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。 
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否 则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复 制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序， 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。 
代码实现

 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 sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
代码实现

 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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Python实现八大排序算法相关文章请关注PHP中文网！