"""  
我的错误写法1  
我根据定义的写法，把第1个定义成基准值，然后进行对比，向前走，最后交换。  
写的什么问题都没有。但其实这里面有个很大的错误。  
那就是指针没有进行定义，直接去拿给的参数进行对比。  
这样造成的错误就是  
while start < end and arr[end] >= pivot:  
IndexError: list index out of range  
"""  
def error_quick_sort(arr, start, end):  
    if start >= end:  
        return   
    pivot = arr[start]  
    while start < end and arr[end] >= pivot:  
        end -= 1  
    arr[start] = arr[end]  

    while start < end and arr[start] < pivot:  
        start += 1  
    arr[end] = arr[start]   
    arr[start] = pivot  

    error_quick_sort(arr,start,pivot - 1)  
    error_quick_sort(arr,pivot + 1, end)  
"""  
我的错误写法2  
乍一看该定义的也定义了。  
但是low和high没有了判断条件就，造成了直接就是排序错误  
"""  
def error_quick_sort(arr, start, end):  
    if start >= end:  
        return   
    pivot = arr[start]  
    low = start  
    high = end  
    while low < high and arr[high] >= pivot:  
        high -= 1  
    arr[low] = arr[high]     
    while low < high and arr[low] < pivot:  
        low += 1  
    arr[high] = arr[low]  
    arr[low] = pivot  

    error_quick_sort(arr,start,low - 1)  
    error_quick_sort(arr,high + 1, end)  

arr = [54,26,93,17,77,31,44,55,20]  
error_quick_sort(arr,0,len(arr)-1)  
print(arr)  

# result  
# [20, 26, 54, 17, 77, 31, 44, 55, 93]  

def quick_sort(arr, start, end):  
    # 递归条件出口  
    if start >= end:  
        return   
    pivot = arr[start]  
    # 定义前后指针  
    low = start  
    high = end  
    # 如果前后2个指针不重合  
    while low < high:  
        # 从后向前走，直到遇到比自己还大的  
        while low < high and arr[high] >= pivot:  
            high -= 1  
        arr[low] = arr[high] # 这时候以high为index的位置是空着的  
         # 从前向后走，直到遇到比自己还小的  
        while low < high and arr[low] < pivot:  
            low += 1  
        arr[high] = arr[low] # 这时候high的位置被填充，但low为index位置为空  

        # 2边这时候都已经无法继续向下走  
        # 我们把中间这个数值和目前已经为空的以low为index的数值进行交换  
        arr[low] = pivot  
    # 这时候继续从左边进行递归，每次都缩小1个index的范围  
    quick_sort(arr,start,low - 1)  
    # 这时候继续从右边边进行递归，每次都增加1个index的范围  
    quick_sort(arr,high + 1, end)  


arr = [54,26,93,17,77,31,44,55,20]  
# end的代指最后一个数值的index，也就是长度-1  
quick_sort(arr,0,len(arr)-1)  
print(arr)  

# result  
# [17, 20, 26, 31, 44, 54, 55, 77, 93]  

# Python program for implementation of Quicksort Sort   
def partition(arr,low,high):   
    i = ( low-1 )  
    pivot = arr[high]  

    for j in range(low , high):   
        if arr[j] <= pivot:   
            i = i+1  
            arr[i],arr[j] = arr[j],arr[i]   

    arr[i+1],arr[high] = arr[high],arr[i+1]   
    return ( i+1 )   

def quick_sort(arr,low,high):   
    if low < high:   
        pi = partition(arr,low,high)   
        quick_sort(arr, low, pi-1)   
        quick_sort(arr, pi+1, high)   

arr = [54,26,93,17,77,31,44,55,20]  
quick_sort(arr,0,len(arr)-1)  
print(arr)  

# result  
# [17, 20, 26, 31, 44, 54, 55, 77, 93]  

def quick_sort(arr):      
    if len(arr) <= 1:          
        return arr      
    pivot = arr[len(arr) // 2]      
    left = [x for x in arr if x < pivot]      
    middle = [x for x in arr if x == pivot]      
    right = [x for x in arr if x > pivot]      
    return quick_sort(left) + middle + quick_sort(right)  

arr = [54,26,93,17,77,31,44,55,20]  
print(quick_sort(arr))  

# result  
# [17, 20, 26, 31, 44, 54, 55, 77, 93]