2022-09-20 快速排序

快速排序

基准 我认为最好是选最右侧的那个，其实，三选一更好。但不好写

la= [1, 2, 4, 7, 11, 6,8,9,34,45,56,67,78,79,99,12,13,14,23,24]
def swap(a,b):
    la[a],la[b]= la[b],la[a]
#右侧为基准
def fast(la,a,e):
    if a<e:
        t=la[e]       
        slow=a
        for f in range(a,e):
            if la[f]<t:
                swap(slow,f)
                slow+=1
        swap(slow,e)
        fast(la,a,slow-1)
        fast(la,  slow+1,e)

fast(la,0,len(la)-1)
print(la)

#左侧为基准
def ss(la,left,r):
    if left<r:
        t=la[left]
        slow=left
        for i in range(left+1,r+1):
            if la[i]<t:
                slow+=1
                la[slow],la[i] =la[i],la[slow]

        la[slow],la[left]=la[left],la[slow]
        ss(la,left,slow-1)
        ss(la,slow+1,r)

la=[3,2,1,6,5,4,9,8,7]
ss(la,0,8)
print(la)
#双指针
def sort(a):
    left =0
    high = r= len(a) - 1
    #分区以右侧为
    def kk(a, left, high):
        if left < high:
            r = high
            p = a[r]
            zuo = left
            while left < high:
               while left < high and a[left] <= p:
                  left += 1

               while left < high and a[high] >= p:
                  high -= 1
               a[left], a[high] = a[high], a[left]

            a[left], a[r] = a[r], a[left]
            p = left
            kk(a, zuo, p - 1)
            kk(a, p + 1, r)

    kk(a, 0, high)