def big_endian(ds, root, end):
    """
    将堆的末端子节点作调整，使得子节点永远小于父节点  
    :param: ds    get_figure2draw  
    :param: root int 开始（list index）  
    :param: end int 结束（list index）  
    """
    arr = ds.data
    child = root * 2 +  1 # 左子节点
    while child <= end: 
        if child + 1 <= end and arr[child] < arr[child + 1] :
        # 判断右child是否存在，如果存在则和另外一个同级节点进行比较
            child += 1
        if arr[root] < arr[child]:
            ds.swap(root, child)
            ## 下钻到下层
            root = child
            child = root * 2 + 1
        else:
            break


def HeapSort(ds):
    """
    堆排序
    """
    Length = ds.length - 1
    first = Length // 2 
    for root in range(first, -1, -1):
    # 建堆
        big_endian(ds, root, Length)
    for end in range(Length, 0, -1):
        # 堆顶是最大的值，放到最末尾，长度-1后继续建堆
        ds.swap(0, end) 
        big_endian(ds, 0, end - 1) 

def CycleSort(ds):
    """
    环排序只适用于整数排序，且数正好范围在[0,N-1]内，且只有少量重复元素，不稳定
    """
    assert isinstance(ds, get_figure2draw), "Type Error"
    assert isinstance(ds.data[0], int), "Type Error"

    Length = ds.length
    dt = ds.data
    # 重复元素的列表
    repeatIdxs = []
    for i in range(Length):
        currIdx = i
        # 查找当前值应该所在的索引 
        shouldIdx = sum([1  if dt[currIdx] > v else 0 for v in  dt ])
        # cycle 跑圈 (忽视重复值)
        while currIdx != shouldIdx and dt[currIdx] != dt[shouldIdx]: # 当前位置不是应该所在的位置的时候
            ds.swap(currIdx, shouldIdx) # 交换 currIdx, shouldIdx 的值
            shouldIdx = sum([1 if dt[currIdx] > v else 0 for v in  dt ])
        # 可能包含重复的值记录
        if dt[currIdx] == dt[shouldIdx] and  currIdx != shouldIdx:
            repeatIdxs.append([currIdx, shouldIdx])
    # 重复元素插值
    for rep in repeatIdxs:
        if dt[rep[0]] == dt[rep[1]]:
            ds.set_val(rep[0], dt[max(rep[0] - 1, 0)])