堆排序

堆排序

堆：heap 一种数据结构 完全二叉树（每个父节点最多只有两个子节点左节点和右结点） 常用来做堆排序和二叉树排序 每一个堆都可以用数组来表示 节点与数组下表对应关系为：

堆顶位置为数组第一个下标    给定一个数组下标i  父节点i =i/2； 左子节点 = i*2 右子节点= 2i+1；

二叉堆一般分为 最大堆 和 最小堆 最大堆是每一个父节点都大于它的子节点 最小堆与之相反

一个堆与数组的对应关系

 堆排序的步骤：

1、先把一个数组表示为一个堆，并且对这个堆进行最大堆排序

2、将排完序的堆顶元素与最后一个元素交换位置并且对交换位置后的堆再次进行堆排序（将倒数第二个元素不断与堆顶元素进行比较构造成最大堆），最后一个元素已经排完序 在对前面的元素进行排序 每次出来一个这次排序最大的元素 

堆排序的C语言版 堆排序第二步

堆排序效率：时间复杂度为（nlogn） 空间复杂度（O（1）） 该排序为不稳定的排序。