C# 排序算法之堆排序

【堆排序】是一种基于比较的排序算法，利用了数据结构中的“堆”这一概念。堆是一种特殊的树形数据结构，可以被视作一棵完全二叉树。在C#中，虽然“堆”不是一个内置的数据结构，但我们可以用数组来模拟堆的结构。 ### 一、堆的基本概念 堆分为两种主要类型：**最大堆**和**最小堆**。在最大堆中，每个父节点的值都大于或等于其子节点的值，而根节点是堆中最大值。相反，最小堆中每个父节点的值都小于或等于其子节点的值，根节点是最小值。数组中，我们可以通过简单的计算公式找到父节点、左孩子和右孩子的索引： - 父节点索引：`parent(i) = i / 2` - 左孩子索引：`left(i) = 2 * i` - 右孩子索引：`right(i) = 2 * i + 1` ### 二、构造最大堆 构造最大堆通常采用自底向上的方法，从叶子节点开始，确保每个子树都是最大堆。如果根节点小于其子节点，就交换它们的位置，然后递归地调整子树，直到整个堆满足最大堆的条件。这个过程被称为**MaxHeapify**。 ### 三、堆排序的实现 堆排序算法通常包括以下几个步骤： 1. **建立最大堆**：从最后一个非叶子节点（数组长度除以2向下取整）开始，调用MaxHeapify函数，确保每个子树都是最大堆。 2. **交换并缩小堆**：将堆顶元素（最大值）与末尾元素交换，然后将堆的大小减一。再次调用MaxHeapify，重新调整堆。重复此过程，直到堆只剩下一个元素。 以下是一个简化的C#代码实现： ```csharp namespace HeapSort { class Program { static int heapSize; static void Main(string[] args) { int[] heap = { -1, 10, 5, 12, 77, 54, 7, 34, 23, 11 }; heapSize = heap.Length - 1; BuildMaxHeap(heap); for (var i = heap.Length - 1; i >= 2; i--) { Swap(heap, 1, i); heapSize--; MaxHeapify(heap, 1); } foreach (var i in heap) Console.Write(i + " "); } static void BuildMaxHeap(int[] heap) { for (var i = (heap.Length - 1) / 2; i >= 1; i--) { MaxHeapfy(heap, i); } } static void MaxHeapify(int[] heap, int index) { int largerItemIndex = index; int leftChildIndex = index << 1; int rightChildIndex = (index << 1) + 1; if (leftChildIndex <= heapSize && heap[leftChildIndex] > heap[index]) { largerItemIndex = leftChildIndex; } if (rightChildIndex <= heapSize && heap[rightChildIndex] > heap[largerItemIndex]) { largerItemIndex = rightChildIndex; } if (largerItemIndex != index) { Swap(heap, index, largerItemIndex); MaxHeapify(heap, largerItemIndex); } } static void Swap(int[] heap, int i, int j) { var temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } } } ``` 这个C#程序展示了如何创建最大堆，交换堆顶元素，并通过不断调整保持堆的性质，从而实现排序。堆排序的时间复杂度为O(n log n)，在某些场景下性能优于其他O(n^2)的排序算法，如冒泡排序和选择排序。但是，由于频繁的交换操作，它的空间效率并不高，不适合处理大量数据。