说明

$将A[p\dots r]划分为A[p\dots q-1]和A[q+1\dots r],使得A[p\dots q-1]的每一个元素都要小于等于A[q],而A[q+1\dots r]每一个元素都要大于等于A[q]，并递归调用，所有操作在原数组上进行，无需归并$

代码

from typing import List,Optional
import math
def quicksort(A:List[int],p:int,r:int):
    if p<r:
        q = partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
def partition(A:List[int],p:int,r:int)->int:
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j]<=x:
            i=i+1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1
A = [2,8,7,1,3,5,6,4]
quicksort(A,0,len(A)-1)
print(A)