06-7堆排序.py

# 顺序存储的大根堆

def sift(li,low,high):
    """
    :param li:列表:
    :param low; 堆的根节点位置:
    :param high:堆的最后一个元素的位置:
    return:  
      
    """

    i= low # i最开始指向根节点
    j=2*i+1  # j 开始是左孩子
    tmp = li[low] #把堆顶存起来
    while j<= high: # 只要i位置有数
        if j + 1 <= high and li[j+1] > li[j]:# 如果右孩子有并且比较大
            j= j + 1 #指向右孩子

        if li[j] > tmp:
            li[i] = li[j]
            i=j #往下看一层
            j=2*i+1

        else:  # tmp更大，把tmp放到i的位置上
            li[i] = tmp #把tmp放到某一级领导位置上
            break
            
    
    else:
        li[i] = tmp # 把tmp放到叶子节点上



#=========堆排序===========================

# 构造堆
def heap_sort(li):
    n = len(li)
    for i in range((n-2)//2,-1,-1):  #根据子节点找父节点 根据规律 左孩子i 则父节点等于(i-1 )//2  因为最后的节点的索引是n- 1  所以将i = n -1  带入得到（n-2）//2
        #i表示建堆的时候调整的部分的根的下标s
        sift(li,i,n-1)
        #建堆完成了

    # 挨个出数
    for i in range(n-1,-1,-1):
        # i 指向当前堆的最后一个元素
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1) # i-1是新的high

 



if __name__ == "__main__":

    import random 

    li = [i for i in range(100)]
    random.shuffle(li) 

    print(li)
    heap_sort(li)
    print(li)