[Python知识库]堆排序及python代码

堆排序过程

def sift(li, low, high):
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        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:
            li[i] = tmp
            break
    else:
        li[i] = tmp

def heap_sort(li):
    n = len(li)
    # 构建堆
    for i in range((n-2)//2,-1,-1):
        # i 表示建堆时候调整的部分根的下标
        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)

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