堆排序 Heap sort算法
堆排序 heap sort，指的是利用数据构造堆完成排序，排序利用的是最大二叉堆 max heap。
最大二叉堆是一棵完备二叉树，知足如下特色：
如图所示：
堆不是线性构造，但常日可以用数组进行表示，由于堆每个节点的索引很随意马虎打算，给定一个节点索引 i，很随意马虎打算出其父节点、左子节点和右子节点的索引：
父节点：i / 2 或 i >> 1左子节点：i 2 或 i << 1右子节点：i 2 + 1 或 i << 1 + 1以上最大堆，可以利用下面的数组表示：
堆排序最关键的步骤是将数组序列最大堆化，思路是供应功能给定一个节点索引，可以将该索引对应的节点及其子节点掩护为知足最大堆的性子，该操作称为最大堆化，是一个递归的操作，思路是：
假定 i 的旁边子节点都知足最大堆特性。存在该假定的情由是我们是从叶子节点向根节点进行最大堆化的。找出 i 和 其旁边节点三个值中的最大值索引 largest。若largest == i，解释 i 已经知足最大堆性子，任务完成。若 largest != i，解释 i 不知足，交流 largest 和 i 的值，然后，递归地对 largest 连续做最大堆化操作。掩护好堆构造后，堆排序就可以基于以上的最大堆完成排序，详细过程是：
先将待排序序列构建为最大堆。此时根元素为最大元素。再将根元素与末了的元素置换，此时最大元素位于末了元素上，最大元素排序完毕。之后将除了末了一个元素的前面元素再次构建为最大堆，然后将最大根元素与倒数第二个元素交换。重复以上步骤，依次将最大元素置换的对应的位置上，直到未排序元素只有1个，排序结束。编码go 1//堆排序 2funcHeapSort(data[]int){ 3//构建最大堆 4BuildMaxHeap(data) 5//掌握知足最大堆元素个数 6size:=len(data) 7//依次获取最大元素，放在序列后 8fori:=len(data)-1;i>=1;i--{ 9//交流根节点和当前元素10data[i],data[0]=data[0],data[i]11//最大堆尺寸-1，后边元素已经排序完成12size-=113//交流元素后，重新最大堆化14maxHeapfy(data,0,size)15}16}17//构建最大堆18funcBuildMaxHeap(data[]int){19//从第一个具有子节点的节点开始构建20l:=len(data)21fori:=l/2;i>=0;i--{22//掩护i节点最大堆23maxHeapfy(data,i,l)24}25}2627//掩护i节点的最大堆性子28//size是末了一个对元素索引29funcmaxHeapfy(data[]int,i,sizeint){30//确定旁边子节点索引31l,r:=i<<1,i<<1+132//判断最大值位于哪个索引33largest:=i34ifl<size&&data[l]>data[largest]{35largest=l36}37ifr<size&&data[r]>data[largest]{38largest=r39}40//若索引i不是最大值41ifi!=largest{42//则交流i和largest索引元素43data[i],data[largest]=data[largest],data[i]44//递归掩护largest元素的最大堆性子45maxHeapfy(data,largest,size)46}47}4849//测试通过50data:=[]int{5,3,8,1,2,7,4,0,9,6}51HeapSort(data)52fmt.Println(data)//[0123456789]PythonJavaScriptPHP剖析
堆排序的韶光繁芜度为 O(nlgn)，同样是原址排序，不须要额外的存储空间。除了最大堆，还有最小堆，最小堆常日用来构建优先行列步队
