def partition(array, low, high):
    """
    快速排序中用到的分割函数：
    重新排序数列，所有比基准值小的元素摆放在基准前面，
    所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。
    在这个分割结束之后，对基准值的排序就已经完成;
    @:param array 传入的数组，一小段
    @:param low 最小索引
    @:param high 最大索引
    @:return 一步分割后的基准值下标
    """
    i = low  # 最小元素索引
    # j 遍历 [low, high)，high 是基准值的下标，所以不包含 high
    for j in range(low, high):
        # 当元素小于或者等于基准值 array[high]
        if array[j] < array[high]:
            # 交换下标 i 和 j 的位置
            if i != j:
                array[i], array[j] = array[j], array[i]
            i += 1
    # 交换位置
    array[i], array[high] = array[high], array[i]
    return i


def quick_sort(array, low, high):
    """
    快速排序
    该函数直接修改了数组的状态
    :param array: 排序数组
    :param low: 起始索引
    :param high: 结束索引
    """
    if low <= high:
        pi = partition(array, low, high)
        quick_sort(array, low, pi - 1)  # 对前半部分排序
        quick_sort(array, pi + 1, high)  # 对后半部分排序


if __name__ == '__main__':
    arrayList = []
    for num in range(100000):
        arrayList.append(uniform(0, 100))

    t1 = time()
    quick_sort(arrayList, 0, len(arrayList) - 1)
    t2 = time()
    print(t2 - t1)
    pass