python排序算法-（6）堆栈排序
堆排序（Heap Sort）是一种树形选择排序算法，其利用了堆的性质进行排序。堆可以看做一个完全二叉树，分为大根堆和小根堆。大根堆满足父节点的值大于等于其子节点的值，小根堆满足父节点的值小于等于其子节点的值。
堆排序的过程可以分为两个步骤：
1. 构建堆：将原始数组转换为一个满足堆性质的堆。可以从最后一个非叶子节点开始，从右到
左，从下至上依次对每个节点执行堆化操作，将原始数组构建成一个堆。
2. 对堆进行排序：将堆顶元素与待排序区间的末尾元素交换位置，然后对新的待排序区间进行
堆化操作，直到整个数组有序。
堆排序的时间复杂度为O(nlogn)，其中堆化操作的时间复杂度为O(logn)，堆排序的空间复杂
度为O(1)。
import random
def heapify(arr, n, i):
largest = i # 初始化最大值下标为当前根结点下标
left = 2 * i + 1
right = 2 * i + 2
# 如果左子项节点存在且大于当前根结点的值，则更新最大值下标为左子项节点下标
if left < n and arr[left] > arr[largest]:
largest = left
# 如果右子项节点存在且大于当前根结点的值，则更新最大值下标为右子项节点下标
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值下标不等于当前根结点下标，则交换两个节点的值，并对被交换的子树递归执行堆化操作
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def build_max_heap(arr):
n = len(arr)
# 从最后一个非叶子节点开始，依次对每个节点执行堆化操作，以构建第一次堆
for j in range(n // 2 - 1, -1, -1):
heapify(arr, n, j)
def heap_sort(arr):
n = len(arr)
build_max_heap(arr) # 构建第一次堆
# 从末尾开始遍历数组，每次将堆顶（最大值）放到待排序区间的末尾，并对新的堆进行堆化操作
for k in range(n - 1, 0, -1):
arr[0], arr[k] = arr[k], arr[0] # 交换堆顶和数组末尾元素的值
heapify(arr, k, 0) # 对新的堆执行堆化操作
# 测试
array=random.sample(range(0, 100), 50)
print("给定的数组为:")
print(array)
heap_sort(array)
print('经过堆排序后的数组为:')
print(array)运行环境：python3.8
给定的数组为:
[54, 43, 0, 26, 17, 33, 93, 56, 60, 4, 51, 48, 88, 71, 75, 16, 97, 95, 77, 45, 80, 98, 36, 91, 55, 94, 13, 14, 6, 61, 3, 67, 79, 28, 23, 78, 29, 5, 39, 35, 96, 31, 49, 87, 50, 20, 66, 18, 9, 92]
经过堆排序后的数组为:
[0, 3, 4, 5, 6, 9, 13, 14, 16, 17, 18, 20, 23, 26, 28, 29, 31, 33, 35, 36, 39, 43, 45, 48, 49, 50, 51, 54, 55, 56, 60, 61, 66, 67, 71, 75, 77, 78, 79, 80, 87, 88, 91, 92, 93, 94, 95, 96, 97, 98]
