快速排序

快速排序使用分治法策略来把一个序列分为较大和较小的2的子序列，然后递归的排序两个子序列

1，挑选基准值
2，分割，小于基准值的放在前面，大于基准值放在后面
3，递归排序子序列

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


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


arr = [10, 22, 78, 3, 12, 9, 1, 11, 33, 2]
low = 0
high = len(arr) - 1
quick_sort(arr, low, high)
print(arr)

总结：从始至终都在一个数组上操作，因为递归，分批选出前序列和后序列。
1->2 ; 2>4 ; ....直至每个小序列排好序，也就是数组元素只有一个时。
选数组最后一个元素为pivot（支点），遍历数组与支点值比较大小，
遍历到较小的值 ，放到前面序列中并记录此刻放入序列的位置。遍历到最后后，返回此刻记录的前序列的位置，此为中指点。
然后递归 排序前面序列和后面序列，也就是此刻 1->2 **
**然后递归重复上述操作 2->4....