Die Grundidee der Schnellsortierung:
Teilen Sie die zu sortierenden Daten in einem Sortierdurchgang in zwei unabhängige Teile auf. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil , und dann drücken Sie diese Methode führt eine schnelle Sortierung dieser beiden Datenteile durch, und der gesamte Sortiervorgang kann rekursiv durchgeführt werden, sodass die gesamten Daten geordnet werden.
Beispiel:
arr = [49,38,04,97,76,13,27,49,55,65], legen Sie die erste Ziffer 49 als Schlüsselwert fest, von rechts um eine Zahl zu finden, die kleiner als der Schlüsselwert auf der linken Seite ist, und die gefundene Zahl der ersten Ziffer zuzuweisen
arr = [27,38,04,97,76,13,27,49,55, 65] Suchen Sie dann die Zahl, die von links nach rechts größer als der Schlüsselwert ist, und weisen Sie die gefundene Zahl der letzten von rechts nach links gefundenen Zahl zu
arr = [27,38,04,97; ,76 ,13,97,49,55,65], dann von rechts nach links, von links nach rechts, bis links=rechts, aus der Schleife ausbrechen und den Schlüsselwert einigen Indexwerten zuweisen. Zum Schluss rekursieren Sie die Gruppen auf beiden Seiten.
Code:
def quick_sort(lists, left, right):
#快速排序
if left >= right: #当递归调用的分组为1个数时返回列表
return lists
key = lists[left] #保存key值，在一轮调用结束时，存到中间值
low = left
high = right #供递归调用时使用
while left < right: #通过下面两个循环依次交替赋值并使key值两侧为大小分组
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) #对key值左侧进行排序分组
quick_sort(lists, left+1, high) #对key值右侧进行排序分组
return lists
