import random
import time

def cal_time(func):
    """
    测试时间装饰器
    :param func: 接收一个函数
    :return:
    """
    def wrapper(*args, **kwargs):
        ti = time.time()
        x = func(*args, **kwargs)
        ti2 = time.time()
        print("time cost:", func.__name__, ti2 - ti)
        return x
    return wrapper


def quick_sort_x(data, left, right):
    if left < right:
        # 将left位置的数字，归位
        mid = partition(data, left, right)
        # 递归操作
        quick_sort_x(data, left, mid - 1)
        quick_sort_x(data, mid + 1, right)


def partition(data, left, right):
    """
    实现归位操作
    :param data: 无序列表
    :param left: 列表左边下标
    :param right: len(data) - 1
    :return:排序后的列表
    """
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return right


@cal_time
def quick_sort(data):
    return quick_sort_x(data, 0, len(data) - 1)

da = list(range(10000))
random.shuffle(da)
quick_sort(da)
print(da)