Heapsort，,#--coding: u

Heapsort，,#--coding: u

#--coding: utf8 --def heapsort(A):    build_max_heap(A)    heap_size = len(A)    for i in range(len(A) - 1, 0, -1):        A[0], A[i] = A[i], A[0]        heap_size = heap_size - 1 # 这里与i相等        max_heapify_iter(A, 0, heap_size)def build_max_heap(A):    heap_size = len(A)    for i in range((heap_size - 1) / 2, -1, -1):        max_heapify_iter(A, i, heap_size)# 运行时间为O(lgn)，是保持最大堆性质的关键# 前提：左右子树都是最大堆# 递归方式def max_heapify(A, i, heap_size):    l = 2 * i + 1 # 数组从0开始计数    r = l + 1    largest = i    if l < heap_size and A[l] > A[i]:        largest = l    if r < heap_size and A[r] > A[largest]:        largest = r    if not largest == i:        A[largest], A[i] = A[i], A[largest]        max_heapify(A, largest, heap_size)# 迭代方式def max_heapify_iter(A, i, heap_size):    while True:        l = 2 * i + 1        r = l + 1        if l < heap_size and A[l] > A[i]:            largest = l        else:            largest = i        if r < heap_size and A[r] > A[largest]:            largest = r        if not largest == i:            A[largest], A[i] = A[i], A[largest]            i = largest        else:            break;if __name__ == "__main__":    # A = [3,9,8,4,5,2,10,18,4]    A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]    heapsort(A)    print(A)#该片段来自于http://byrx.net