快速排序

快速排序舞蹈

方法一

def quickSort(array, start, end):
    i = start
    j = end
    # i与j重合时，一次排序结束
    if i > j: 
        return
    flag = array[start]
    while i < j:
        while i < j and array[j] >= flag:
            j -= 1
        # 找到右边第一个小于基准的数, 交换给左边i。此时左边i被记录在flag中
        array[i] = array[j]
        while i < j and array[i] <= flag:
            i += 1
        # 找到左边第一个大于基准的数，交换给右边的j。右边的j的值和上面左边的i的值相同
        array[j] = array[i]
    # 由于循环以i结尾，循环完毕后把flag值交换到i所在位置。
    array[i] = flag
    # 除去i之外两段递归
    quickSort(array, start, i -1)
    quickSort(array, i + 1, end)

array = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
quickSort(array, 0, len(array)-1)
print(array)