Pythons schnelle Sortiermethode

Dieser Artikel stellt hauptsächlich den in Python implementierten Schnellsortierungsalgorithmus vor und analysiert die Prinzipien, Implementierungsmethoden und zugehörigen Betriebstechniken der Python-Schnellsortierung in Form von Beispielen

Die Beispiele in diesem Artikel beschreiben den in Python implementierten Schnellsortierungsalgorithmus. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Die Grundidee der schnellen Sortierung besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile und alle Daten in einer zu teilen Ein Teil ist höher als alle Daten im anderen Teil. Verwenden Sie dann diese Methode, um die beiden Teile der Daten schnell zu sortieren, sodass die gesamten Daten zu einer geordneten Sequenz werden .

Wählen Sie beispielsweise in der Reihenfolge [6, 8, 1, 4, 3, 9] 6 als Basiszahl aus. Scannen Sie von rechts nach links und suchen Sie nach einer Zahl, die kleiner als die Basiszahl 3 ist, vertauschen Sie die Positionen von 6 und 3, [3, 8, 1, 4, 6, 9], scannen Sie dann von links nach rechts und suchen Sie nach einer Zahl größer als die Basiszahl Die Zahl ist 8, vertauschen Sie die Positionen von 6 und 8, [3, 6, 1, 4, 8, 9]. Wiederholen Sie den obigen Vorgang, bis die Zahlen links von der Basiszahl kleiner und die Zahlen rechts davon größer sind. Führen Sie dann die obige Methode rekursiv für die Sequenzen links und rechts von der Referenznummer aus.

Der Implementierungscode lautet wie folgt:

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

Laufergebnisse:

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

Das obige ist der detaillierte Inhalt vonPythons schnelle Sortiermethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!