[PYTHON] Schnelle Sortierdetails und Codebeispiele

Was ist schnelle Sortierung?

Drehen Sie die Elemente (Referenz) und platzieren Sie die verbleibenden Elemente hin und her, je nachdem, ob sie größer oder kleiner als der Drehpunkt sind.

Die Arbeit, den Drehpunkt zu bestimmen und die vorher und nachher angeordneten Elemente anzuordnen, wird wiederholt.

Bestätigen Sie, wann die Elemente eins werden.

** ▼ Beim Einstellen des ersten zu schwenkenden Elements ** 

Schneller Sortierfluss

1. Bestimmen Sie den Drehpunkt und sortieren Sie ihn hin und her, je nachdem, ob er größer oder kleiner als dieser Wert ist. Der Wert und die Position des Drehpunkts sind festgelegt.
2. Führen Sie Prozess 1 für das vorherige Array erneut aus.
3. Führen Sie Vorgang 1 für das hintere Array erneut aus.
4. Der Drehpunkt wird in den Prozessen von 2 und 3 immer mehr fixiert, und schließlich werden alle Elemente fixiert.

## Wenn ganz links der Drehpunkt ist

python

##Geben Sie den Drehpunkt und links + Drehpunkt an+Eine Funktion (schnell), die ein auf der rechten Seite sortiertes Array erstellt_sort）
def quick_sort(arr):
  #Die Sortierung endet, wenn nur ein Element vorhanden ist (eine Sortierung ist nicht erforderlich, wenn weniger als zwei Elemente vorhanden sind).
  if len(arr) <= 1 :
    return arr
  #Geben Sie den Wert von Pivot an
  p = arr[0]

  #Führt den Teilungsprozess basierend auf dem Drehpunkt durch. div Funktion
  arr1, arr2 = div(p, arr[1:])

  #Kombinieren Sie die geteilten Arrays mit Bezug auf den Pivot.
  #Schnell auf das geteilte Array selbst_Führen Sie eine Sortierung durch.
  return quick_sort(arr1) + [p] + quick_sort(arr2)



##Eine Funktion, die basierend auf dem Pivot linke und rechte Arrays erstellt(div)
def div(p, arr):
  #Definieren Sie eine Variable, um das linke und das rechte Pivot-Array zu platzieren
  left, right=[], []

  for i in arr:
    #Auf der linken Seite aufbewahren, wenn es kleiner als der Drehpunkt ist
    if i < p:
      left.append(i)
    #Wenn es sich über dem Drehpunkt befindet, lagern Sie es auf der rechten Seite
    else:
      right.append(i)

  #Linke und rechte Arrays ausgeben
  return left, right

Es ist intuitiver und einfacher zu verstehen als das Zusammenführen von Sortierungen.

• Vorsicht Wenn der Wert ganz links auf Pivot eingestellt ist, erhöht sich der Rechenaufwand, wenn die Werte bereits in absteigender Reihenfolge angeordnet sind.

Aus diesem Grund wird empfohlen, den Pivot zufällig zu bestimmen.

## Schnelle Sortierung, wenn der Drehpunkt zufällig bestimmt wird Verwenden Sie numpys random.choice (Array).

Ändern Sie den Drehpunkt der obigen Funktion quick_sort wie folgt.

python

import numpy as np
  p = random.choice(arr)

quick_sort

import numpy as np

def quick_sort2(arr):
  #Die Sortierung endet, wenn nur ein Element vorhanden ist (eine Sortierung ist nicht erforderlich, wenn weniger als zwei Elemente vorhanden sind).
  if len(arr) <= 1 :
    return arr

  #Geben Sie den Wert von Pivot an
  p = random.choice(arr)

  #Führt den Teilungsprozess basierend auf dem Drehpunkt durch. div Funktion
  arr1, arr2 = div(p, arr[1:])

  #Kombinieren Sie die geteilten Arrays mit Bezug auf den Pivot.
  #Schnell auf das geteilte Array selbst_Führen Sie eine Sortierung durch.
  return quick_sort(arr1) + [p] + quick_sort(arr2)