【Python】快速排序

def partition(arr, low, high):
    '''
    遍历【low,high】区间，把比privot小的依序房放在左边
    遍历完成后，将privot左边一系列小的数的右边一个位置
    这样，左边的都比privot小，右边的都比privot大
    因为列表的传入可以看成是地址传入，所以会实际改变列表
    :param arr: 数据列表
    :param low:
    :param high:
    :return: 中间位置
    '''
    i = low
    pivot = arr[high]

    for j in range(low, high):

        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i = i + 1

    arr[i], arr[high] = arr[high], arr[i]
    return i


def quickSort(arr, low, high):
    '''
    不断的分成左右两个系列，知道low 和 high相等
    :param arr:
    :param low:
    :param high:
    :return:
    '''
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


arr = [10, 7, 8, 9, 1, 5, 45, 6, 56]
n = len(arr)
quickSort(arr, 0, n - 1)
print("排序后的数组:")
for i in range(n):
    print("%d" % arr[i]),

时间复杂度：o(nlogn)

https://blog.csdn.net/A_BlackMoon/article/details/81064712