def partition(array, low, high):
??? """
??? 快速排序中用到的分割函數(shù)：
??? 重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，
??? 所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）。
??? 在這個分割結(jié)束之后，對基準(zhǔn)值的排序就已經(jīng)完成;
??? @:param array 傳入的數(shù)組，一小段
??? @:param low 最小索引
??? @:param high 最大索引
??? @:return 一步分割后的基準(zhǔn)值下標(biāo)
??? """
??? i = low? # 最小元素索引
??? # j 遍歷 [low, high)，high 是基準(zhǔn)值的下標(biāo)，所以不包含 high
??? for j in range(low, high):
??????? # 當(dāng)元素小于或者等于基準(zhǔn)值 array[high]
??????? if array[j] < array[high]:
??????????? # 交換下標(biāo) 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):
??? """
??? 快速排序
??? 該函數(shù)直接修改了數(shù)組的狀態(tài)
??? :param array: 排序數(shù)組
??? :param low: 起始索引
??? :param high: 結(jié)束索引
??? """
??? 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