排序算法-堆排序
1、堆
堆在形式上是一棵完全二叉树（假设树的高度是h，所有的叶子结点都是在第h层或h-1层）
堆分为两类，大根堆和小根堆：
- 大根堆：每个结点的值都大于等于其孩子结点的值；
- 小根堆：每个结点的值都小于等于其孩子结点的值；
堆在形式上是一棵完全二叉树，用数组存储它，不会浪费空间；
2、堆排序的过程
（1）从无序序列所确定的完全二叉树的第一个非叶子结点开始，从右到左，从下到上，对每个结点进行调整，最终得到一个大（小）顶堆。
（2）将根结点a与无序序列中最后一个元素b交换，a进入有序序列，结点b不满足堆，进行调整。
（3）重复（2），直到无序序列只剩下1个，排序结束。
3、算法实现
def sift(arr, i, n): j = 2*i + 1temp = arr[i]while j < n:if j + 1 < n and arr[j] < arr[j+1]:j += 1if temp >= arr[j]:breakarr[i] = arr[j]i = jj = 2*i+1 arr[i] = temp
def heap_sort(arr):if not arr or len(arr) <= 1:returnn = len(arr)for i in range(n//2-1, -1, -1): # 建堆sift(arr, i, n)for i in range(n, 0, -1):arr[0], arr[i-1] = arr[i-1], arr[0] # 堆顶和最后一个无序元素交换位置sift(arr, 0, i-1) # 调整堆if __name__ == '__main__':a = [10, 1, 5, 2, 4, 3, 2, 1]
# a = [5, 8, 7, 6, 3, 2, 1]heap_sort(a)print(a)4、复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(1)