Quick sort

Quick sort ideas ：

• Go to an element p( The first element in the list ), Is element homing
• The list is divided into two parts , It's all on the left p Small , On the right, it's more than p Big
• Recursive completion sorting
  

partition function ： Homing function , Calculate the subscript position of the intermediate value

every last partition The time complexity of the function is logn, Altogether n Time

So the time complexity of quick sort is O(nlogn)（ At best ）

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:   # Look for... From the right tmp Small number 
            right -= 1          # Take a step to the left 
        li[left] = li[right]    # Write the value on the right in the space on the left 
        print(li, 'right')
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]   # Write the value on the left in the space on the right 
        print(li, 'left')
    li[left] = tmp       # After the two values are equal tmp place 
    return left       # return mid Value 

def quick_sort(li, left, right):
    if left < right:    # At least two elements 
        mid = partition(li, left, right)
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)

li=[5,7,4,6,3,1,2,9]
quick_sort(li, 0, len(li)-1)
print(li)



# result 
[2, 7, 4, 6, 3, 1, 2, 9, 8] right
[2, 7, 4, 6, 3, 1, 7, 9, 8] left
[2, 1, 4, 6, 3, 1, 7, 9, 8] right
[2, 1, 4, 6, 3, 6, 7, 9, 8] left
[2, 1, 4, 3, 3, 6, 7, 9, 8] right
[2, 1, 4, 3, 3, 6, 7, 9, 8] left
[1, 1, 4, 3, 5, 6, 7, 9, 8] right
[1, 1, 4, 3, 5, 6, 7, 9, 8] left
[1, 2, 3, 3, 5, 6, 7, 9, 8] right
[1, 2, 3, 3, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 9, 8] right
[1, 2, 3, 4, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 9, 8] right
[1, 2, 3, 4, 5, 6, 7, 9, 8] left
[1, 2, 3, 4, 5, 6, 7, 8, 8] right
[1, 2, 3, 4, 5, 6, 7, 8, 8] left
[1, 2, 3, 4, 5, 6, 7, 8, 9]