堆排序是选择排序的一种改进版本，利用完全二叉树的性质来实现排序，核心逻辑是先构建大顶堆，再逐步将堆顶元素与末尾元素交换，重新调整堆结构，最终得到升序序列。本文会逐步讲解C#中实现堆排序的完整过程。
堆排序的核心原理
堆排序依赖二叉堆结构，二叉堆是完全二叉树，分为大顶堆和小顶堆。大顶堆的特点是每个节点的值都大于或等于其左右子节点的值，堆顶元素是最大值。堆排序升序排列时通常使用大顶堆，降序排列时使用小顶堆。
堆排序的整体流程可以分为三个核心步骤：
- 构建初始大顶堆：将无序数组调整为一个大顶堆结构
- 交换堆顶与末尾元素：将当前堆顶的最大值放到数组末尾
- 调整剩余堆结构：将剩余未排序的元素重新调整为大顶堆，重复交换和调整步骤直到排序完成
C#实现堆排序的步骤拆分
步骤1：实现堆调整方法
堆调整是堆排序的核心操作，作用是将以某个节点为根的子树调整为大顶堆。假设数组下标从0开始，那么对于下标为i的节点，其左子节点下标为2*i+1，右子节点下标为2*i+2。
/// <summary>
/// 调整指定下标的节点为大顶堆
/// </summary>
/// <param name="arr">待调整的数组</param>
/// <param name="i">当前要调整的节点下标</param>
/// <param name="heapSize">当前堆的有效元素数量</param>
private static void Heapify(int[] arr, int i, int heapSize)
{
int largest = i; // 假设当前节点是最大值
int left = 2 * i + 1; // 左子节点下标
int right = 2 * i + 2; // 右子节点下标
// 如果左子节点存在且大于当前最大值，更新最大值下标
if (left < heapSize && arr[left] > arr[largest])
{
largest = left;
}
// 如果右子节点存在且大于当前最大值，更新最大值下标
if (right < heapSize && arr[right] > arr[largest])
{
largest = right;
}
// 如果最大值不是当前节点，交换位置并递归调整受影响的子树
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
Heapify(arr, largest, heapSize);
}
}
步骤2：构建初始大顶堆
构建大顶堆时，需要从最后一个非叶子节点开始，从下往上依次对每个节点进行堆调整。最后一个非叶子节点的下标为arr.Length / 2 - 1。
/// <summary>
/// 构建初始大顶堆
/// </summary>
/// <param name="arr">待构建的数组</param>
private static void BuildMaxHeap(int[] arr)
{
int heapSize = arr.Length;
// 从最后一个非叶子节点开始向上调整
for (int i = heapSize / 2 - 1; i >= 0; i--)
{
Heapify(arr, i, heapSize);
}
}
步骤3：实现完整堆排序方法
完成大顶堆构建后，循环将堆顶元素与堆末尾元素交换，然后缩小堆的有效范围，重新调整堆结构即可完成排序。
/// <summary>
/// 堆排序主方法
/// </summary>
/// <param name="arr">待排序的数组</param>
public static void HeapSort(int[] arr)
{
if (arr == null || arr.Length <= 1)
{
return;
}
// 1. 构建初始大顶堆
BuildMaxHeap(arr);
int heapSize = arr.Length;
// 2. 循环交换堆顶和末尾元素，调整堆结构
for (int i = arr.Length - 1; i > 0; i--)
{
// 交换堆顶元素（下标0）和当前末尾元素（下标i）
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 堆的有效范围缩小，调整剩余元素为大顶堆
heapSize--;
Heapify(arr, 0, heapSize);
}
}
堆排序测试与结果验证
我们可以编写一个测试方法验证堆排序的正确性，输入一个无序数组，调用HeapSort方法后输出排序结果。
using System;
class Program
{
static void Main(string[] args)
{
int[] testArr = { 4, 10, 3, 5, 1, 8, 2, 7, 6, 9 };
Console.WriteLine("排序前数组：");
Console.WriteLine(string.Join(", ", testArr));
HeapSort(testArr);
Console.WriteLine("排序后数组：");
Console.WriteLine(string.Join(", ", testArr));
}
// 这里粘贴前面定义的HeapSort、BuildMaxHeap、Heapify方法
}
运行上述代码后，输出结果如下：
排序前数组：4, 10, 3, 5, 1, 8, 2, 7, 6, 9
排序后数组：1, 2, 3, 4, 5, 6, 7, 8, 9, 10
堆排序的特性分析
堆排序的时间复杂度稳定在O(nlogn)，不管输入数组是有序、逆序还是无序，时间复杂度都不会发生变化，这是它相比快速排序的优势。同时堆排序是原地排序算法，空间复杂度为O(1)，不需要额外的存储空间。
不过堆排序是不稳定的排序算法，相等元素的相对位置可能会发生改变。在实际开发中，如果需要稳定的排序或者数据量较小，可以选择其他排序算法，大规模数据且对空间要求较高的场景下，堆排序是很好的选择。