十大排序、七大查找算法python实现——堆排序(heap sort)

 

 

def adjust_heap(L, i):
    n = len(L)
    if i >= n/2:
        return L
    left_index = 2 * i + 1
    right_index = 2 * i + 2
    
    max_index = i
    
    if left_index < n and L[left_index] > L[max_index]:
        max_index = left_index
    if right_index < n and L[right_index] > L[max_index]:
        max_index = right_index
    if max_index != i:
        L[i], L[max_index] = L[max_index], L[i]
        return adjust_heap(L, max_index)
    else:
        return L

def build_heap(L):
    n = len(L)
    for i in range(n>>1)[::-1]:
        L = adjust_heap(L, i)
    print("build heap: {}".format(L))

# 堆排序
def heap_sort(lists):
    n = len(lists)
    build_heap(lists)
    for i in range(0, n)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        print(lists)
        lists = adjust_heap(lists[:i], 0) + lists[i:]
    return lists

 

 

if __name__ == '__main__':
    #nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    nums = random_list(1,99,20)
    result = heap_sort(nums)