[一鸟飞从过，万仗霓虹醒] 偷图

堆排序（Heap Sort）

堆介绍

想要了解堆排序，就必须得先知道堆是什么： 堆通常是一个可以被看做一棵完全二叉树的数组对象。 完全二叉树是指： 1.每一个节点最多只有两个子节点(二叉树) 2.只有上一层满了，才能有下一层 3.只能从从左到右依次排序 堆有两种： 大顶堆：每个父节点都大于子节点(比如50大于45，40) 小顶堆：每个父节点都小于子节点(比如10小于20，15)

堆排序逻辑

简单来讲，堆排序的要点在于(以下特指从小到大排序)： 1.构造大顶堆，即将最大数字上浮到最上面的根节点上 2.将最大值取出放置最后 3.调整堆至大顶堆(就是重复第一步)

所以自然最重要的是如何构造大顶堆：

.找出当前数组的最后非叶子节点 非叶子节点是指，有子节点的节点，最后非叶子节点的序号n/2-1 十大排序算法----堆排序（最后一个非叶子节点的序号是n/2-1的推理） 使用该节点与两个孩子节点进行比较，将大数上浮到非叶子节点上 类似三个数字比较，取得最大值 继续上述步骤，只是第一步骤需要往前移动一位节点(二叉树的节点)

再偷图

代码

总代码

public int[] HeapSort3(int[] array) { //获取最大数组下标 int heapSize = array.Length - 1; //for循环 for (int i = heapSize; i >= 0; i--) { //构建大顶堆 BuilderMaxHeap3(array, i); //将第一个数据与最后一个数据进行调整 swap(array, 0, i); } return array; }

构建大顶堆

private void builderMaxHeap(int[] array, int heapSize) { //获取最后一个非叶子节点(因为是索引，必须加+1) int parser = (int)Math.Floor((double)((heapSize + 1) / 2 - 1)); //for循环，从下往上依次构建 for (int i = parser; i >= 0; i--) { //调整大顶堆 MaxHeapify3(array, i, heapSize); } }

此处是因为用的是索引，所以需要在"n/2-1"的基础上，n需要加一

调整堆(大数上浮)

private void MaxHeapify3(int[] array, int index, int heapSize) { var iMax = index; var iLeft = 2 * index + 1;//index节点的左子节点 var iRight = 2 * (index + 1);//index节点的右子节点 //如果左节点大于index节点，则大值为左节点 if (iLeft <= heapSize && array[index] < array[iLeft]) { iMax = iLeft; } //如果右节点大于index节点，则大值为右节点 if (iRight <= heapSize && array[iMax] < array[iRight]) { iMax = iRight; } //大值不为index节点，则交换，并重新调整 if (iMax != index) { swap(array, iMax, index); } }

偷图源