所谓堆排序，就是将数组元素组成一个包含左右子节点的树，与之前使用的结构（如下所示相同）
public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } }但我们并不是生成一个实体的TreeNode，而是根据数组中元素的位置去判断该元素是叶子节点，还是非叶子节点。 假如数组为 [4,1,2,6,5,8,7] 对应数组下标分别为**[0,1,2,3,4,5,6]** 我们先来找规律，假设我们的任意位置i,那么如何找到i元素对应的左右节点的数组对应下标位置呢？ 这里注意，组成的树我们是按照广度遍历去组成树的。可以组成如下图所示的树形结构。 参考途中所示，你会发现一个规律，所有的一横排的子树数量，比他所有的父节点的数量和都多一。 第一排为1个，第二排为2个。 2-1 第二排为2个+第一排为1个，第三排为4个。4-3 以此类推… 由上面的规律，我们可以算出，最大的非叶子节点为arr.length/2-1; 还有一个规律，就是一个父节点下标为i，那么该元素左子节点为arr[2i+1]，右子节点为 arr[2i+2] 之所以在这里写下这两个规律，是因为我们的堆排序中需要使用这两个规律。为了避免看到代码不理解，先将规律写在上方。
接下里就是代码，我怕各位不好直接理解，代码我会从最后被调用的代码开始写。
首先交换数组中的两个元素的代码 这个应该很好理解，交换数组中的两个节点值。
/// <summary> /// 交换数组中的两个元素 /// </summary> /// <param name="nums"></param> /// <param name="a"></param> /// <param name="b"></param> public void Swap(ref int a, ref int b) { int temp = a; a = b; b = temp; }大顶推的调整 不要考虑的太复杂，比方一个树形结构，组成数组为[2,3,1]。父节点为2，左子节点为3，右子节点为1。我们需要做的就是找到这三个元素组成结构中最大的位置。显然数组中的第二个元素最大。我们交换用前面的Swap方法去交换父节点和左节点值为3的元素。就构成了一次大顶堆的调整。 这里还要考虑一下，我们是从最后一个父节点向前调整的，当交换数组结构后，有可能会对我们之前已经调整的结构打乱。因此这里加一个递归，判断被移动到下面的节点和所有的子节点大小。 代码如下
/// <summary> /// 大顶推的调整 针对根节点以及根节点下所有被改变的节点 /// </summary> /// <param name="nums">数组</param> /// <param name="currentIndex">要调整的根节点位置</param> /// <param name="Numslength">要调整的数组的长度</param> public void heapify(int[] nums,int currentIndex,int Numslength) { //左节点位置 int left = currentIndex * 2 + 1; //右节点位置 int right = currentIndex * 2 + 2; //记录父节点，左子节点，右子节点中最大的节点位置 我们默认先给父节点 int largePosition = currentIndex; //判断左节点和根节点 if (left<Numslength&&nums[left]>nums[largePosition]) { largePosition = left; } //判断右节点和根节点 if (right<Numslength&& nums[right] > nums[largePosition]) { largePosition = right; } if (largePosition!=currentIndex) { Swap(ref nums[currentIndex],ref nums[largePosition]); //我们是从最后一个父节点向前调整的，当交换数组结构后，有可能会对我们之前已经 //调整的结构打乱。因此这里加一个递归，此时largePosition位置为被移动的父节点。 //判断父节点和所有的子节点大小 heapify(nums, largePosition, Numslength); } }循环所有的非叶子节点 构建一个大顶堆 如何将一整棵树形结构都构建成大顶堆呢，当然是遍历所有的非叶子节点，非叶子节点的数量我们已经介绍完了nums.Length / 2 - 1。代码如下
/// <summary> /// 循环所有的非叶子节点 构建一个大顶堆 /// </summary> /// <param name="nums"></param> public void buildMaxHeap(int[] nums) { //最大的非叶子节点为nums.Length / 2 - 1，我们从最后一个向前遍历 for (int i = nums.Length / 2 - 1; i >= 0; i--) { heapify(nums,i,nums.Length); //调整大顶堆 } }堆排序 到了对获取排序的时候了，当我们构建了大顶堆的时候，顶层元素nums[0]一定为最大的，我们将最大元素与数组末尾依次交换，再调用heapify，此时我们需要排序的根节点是nums[0]的位置，因为我们将子节点上移至最上面，但我们要调整的数组的长度，为我们将数组长度减去最大元素移动末尾的次数。
/// <summary> /// 堆排序 /// </summary> /// <param name="nums"></param> public void HeapSort(int[] nums) { //我们先创建一个大顶堆 buildMaxHeap(nums); //堆顶元素nums[0]为最大元素 ，所以我们将堆顶的元素与数组最后的元素交换 //调用heapify，对交换后的最顶层元素进行重新的排序 //但此时我们传入的要调整的数组的长度就减去一位。 for (int i = nums.Length-1; i > 0; i--) { Swap(ref nums[0],ref nums[i]); heapify(nums, 0, i); } }堆排序整体代码如下
/// <summary> /// 堆排序 /// </summary> /// <param name="nums"></param> public void HeapSort(int[] nums) { //我们先创建一个大顶堆 buildMaxHeap(nums); //堆顶元素nums[0]为最大元素 ，所以我们将堆顶的元素与数组最后的元素交换 //调用heapify，对交换后的最顶层元素进行重新的排序 //但此时我们传入的要调整的数组的长度就减去一位。 for (int i = nums.Length-1; i > 0; i--) { Swap(ref nums[0],ref nums[i]); heapify(nums, 0, i); } } /// <summary> /// 循环所有的非叶子节点 构建一个大顶堆 /// </summary> /// <param name="nums"></param> public void buildMaxHeap(int[] nums) { //最大的非叶子节点为nums.Length / 2 - 1，我们从最后一个向前遍历 for (int i = nums.Length / 2 - 1; i >= 0; i--) { heapify(nums,i,nums.Length); //调整大顶堆 } } /// <summary> /// 大顶推的调整 针对根节点以及根节点下所有被改变的节点 /// </summary> /// <param name="nums">数组</param> /// <param name="currentIndex">要调整的根节点位置</param> /// <param name="Numslength">要调整的数组的长度</param> public void heapify(int[] nums,int currentIndex,int Numslength) { //左节点位置 int left = currentIndex * 2 + 1; //右节点位置 int right = currentIndex * 2 + 2; //记录父节点，左子节点，右子节点中最大的节点位置 我们默认先给父节点 int largePosition = currentIndex; //判断左节点和根节点 if (left<Numslength&&nums[left]>nums[largePosition]) { largePosition = left; } //判断右节点和根节点 if (right<Numslength&& nums[right] > nums[largePosition]) { largePosition = right; } if (largePosition!=currentIndex) { Swap(ref nums[currentIndex],ref nums[largePosition]); //我们是从最后一个父节点向前调整的，当交换数组结构后，有可能会对我们之前已经 //调整的结构打乱。因此这里加一个递归，此时largePosition位置为被移动的父节点。 //判断父节点和所有的子节点大小 heapify(nums, largePosition, Numslength); } } /// <summary> /// 交换数组中的两个元素 /// </summary> /// <param name="nums"></param> /// <param name="a"></param> /// <param name="b"></param> public void Swap(ref int a, ref int b) { int temp = a; a = b; b = temp; }