堆排序的思想

# coding: utf-8
# 时间复杂度:O(nlogn)  空间复杂度:O(1)原地排序  大顶堆

import random
import math

#随机生成0~100之间的数值
def get_andomNumber(num):
    lists=[]
    i=0
    while i<num:
        lists.append(random.randint(0,100))
        i+=1
    return lists


# 调整堆
# 递归的调整
def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i  # 堆顶
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

# 创建堆
def build_heap(lists, size):
    for i in range(0, (int(size/2)))[::-1]:
        adjust_heap(lists, i, size)

# 堆排序
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    # for i in range(0, size)[::-1]:   # 这种写法也证明range生成的是一个序列
    for i in range(size-1, 0, -1):   # 这两句等价
        lists[0], lists[i] = lists[i], lists[0]   # 堆顶元素与首元素交换
        adjust_heap(lists, 0, i)  # 交换后，需要对完全二叉树进行调整
        # 这里注意是(0, i) 相当于堆顶元素变了，因为以后调整好就不再动它了!!\
        # 这也是为什么i需要逆序的原因了
    return lists




a = get_andomNumber(6)
print("排序之前：%s" %a)

b = heap_sort(a)

print("排序之后：%s" %b)