2019-05-21

关于算法图解 p52 快速排序，python写一下

listk=[1,3,4,2,7,5,6,8,9,2,3,89,56,45,34,24,7]



def quicksort(arr):
    if len(arr)<2:return arr
    #if len(arr)<2:return arr[0]
    else:
        pp=arr[0]
        left=[x for x in arr[1:] if x<=pp]
        #left=[x for x in arr if x<=pp]
        
        right =[y for y in arr[1:] if y>pp]
        #right =[y for y in arr if y>pp]
        #return quicksort(left)+[pp]+quicksort(right)
    return quicksort(left)+[pp]+quicksort(right)
    #return quicksort(left)+pp+quicksort(right)

def quicksort2(arr):
    if len(arr)<2:return arr
    #if len(arr)<2:return arr[0]
    else:
        pp=arr[-1]
        left=[x for x in arr[:-1] if x<=pp]
        #left=[x for x in arr if x<=pp]
        
        right =[y for y in arr[:-1] if y>pp]
        #right =[y for y in arr if y>pp]
        #return quicksort(left)+[pp]+quicksort(right)
    return quicksort2(left)+[pp]+quicksort2(right)
    #return quicksort(left)+pp+quicksort(right)


print quicksort(listk)
print quicksort2(listk)

把容易犯错的几个地方，用注释写出了。