#快速排序算法, 1、递归实现 2、任务拆分子任务 3、起止条件 4、sample data 
# input: arr = [3, 7, 1, 9, 2, 5]， 左边和右边交替，左边只要找打比3小的就交换，再走右边
#描述：
        
#快速排序算法
def quick_sort(arr, start, end):
    if start >= end:
        return
    pivot = arr[start]
    left = start + 1
    right = end
    while left <= right:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and arr[right] >= pivot:
            right -= 1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    arr[start], arr[right] = arr[right], arr[start]
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)

arr = [3, 7, 1, 9, 2, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 5, 7, 9]