【数据结构与算法Python实践系列】5分钟学会经典排序算法-堆排序

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 时间复杂度O(N*logN)
• 空间复杂度O(1)
• 不稳定排序：比如一个数组222，我们建立大根堆时，堆顶元素会换到最后的位置上去，导致第一个2排序后跑到了最后面，破坏了数据的稳定性。

算法的原理

首先是把数组建中的N个数建成一个大小为N的大根堆，堆顶元素数树的最大值，将堆顶元素与堆的最后一个元素进行位置互换，然后把最大值脱离出堆结构，放在数组的最后位置，作为数组的有序部分；然后对n-1的堆进行位置调整，把最大值放在堆顶；再重复堆顶数据与堆的最后一位进行位置交换，存入有效部分，当堆的大小为1的时候，数据就变得有序了。 Python实现

# 堆排序
def