堆排序——C#实现一算法描述堆排序（Heap Sort）是利用一种被称作二叉堆的数据结构进行排序的排序算法。
二叉堆在内部维护一个数组，可被看成一棵近似的完全二叉树，树上每个节点对应数组中的一个元素。
除最底层外，该树是满的。
二叉堆中，有两个与所维护数组相关的属性。
Length表示数组的元素个数，而HeapSize则表示二叉堆中所维护的数组中的元素的个数（并不是数组中的所有元素都一定是二叉堆的有效元素）。
因此，根据上述定义有： 0 = HeapSize = Length。
二叉堆可分为最大堆和最小堆两种类型。
在最大堆中，二叉树上所有的节点都不大于其父节点，即 A[Parent(i)] = A[i]。
最小堆正好相反：A[Parent(i)] = A[i]。
为维护一个二叉堆是最大（小）堆，我们调用一个叫做MaxHeapify （MinHeapify）的过程。
以MaxHeapify，在调用MaxHeapify时，先假定根节点为Left(i)和Right(i)的二叉树都是最大堆，如果A[i]小于其子节点中元素，则交换A[i]和其子节点中的较大的元素。
但这样一来，以被交换的子节点为根元素的二叉堆有可能又不满足最大堆性质，此时则递归调用MaxHeapify方法，直到所有的子级二叉堆都满足最大堆性质。
如下图所示：因为在调用MaxHeapify（MinHeapify）方法使根节点为A[i]的二叉堆满足最大（小）堆性质时我们有其左右子堆均已满足最大（小）堆性质这个假设，所以如果我们在将一个待排序的数组构造成最大（小）堆时，需要自底向上地调用 MaxHeapify（MinHeapify）方法。
在利用最大堆进行排序时，我们先将待排序数组构造成一个最大堆，此时A[0]（根节点）则为数组中的最大元素，将A[0]与A[n - 1]交换，则把A[0]放到了最终正确的排序位置。
然后通过将HeapSize 减去1，将（交换后的）最后一个元素从堆中去掉。
然后通过MaxHeapify方法将余下的堆改造成最大堆，然后重复以上的交换。
重复这一动作，直到堆中元素只有2个。
则最终得到的数组为按照升序排列的数组。
二算法实现1 注意到在C#中数组的起始下标为0，因此，计算一个给定下标的节点的父节点和左右子节点时应该特别小心。
private static int Parrent(int i)return (i - 1) - 2;private static int Left(int i)return 2 * i + 1;private static int Right(int i)return 2 * i + 2;2 算法的核心部分是MaxHeapify（MinHeapify）方法，根据算法描述中的说明，一下代码分别实现了对整数数组的最大堆化和最小堆化方法，以及一个泛型版本。
private static void MaxHeapify(int[] array, int i, int heapSize)int left = Left(i);int right = Right(i);int largest = i;if (left heapSize array[left] array[i])largest = left;if (right heapSize array[right] array[largest])largest = right;if (largest != i)Exchange(ref array[i], ref array[largest]);MaxHeapify(array, largest, heapSize);private static void MinHeapify(int[] array, int i, int heapSize)int left = Left(i);int right = Right(i);int smallest = i;if (left heapSize array[left] array[i])smallest = left;if (right heapSize array[right] array[smallest])smallest = right;if (smallest != i)Exchange(ref array[i], ref array[smallest]);MinHeapify(array, smallest, heapSize);private static void MHeapifyT(T[] array, int i, int heapSize, ComparisonT comparison)int left = Left(i);int right = Right(i);int extremumIndex = i;if (left heapSize comparison(array[left], array[i]) 0) extremumIndex = left;if (right heapSize comparison(array[right], array[extremumIndex]) 0)extremumIndex = right;if (extremumIndex != i)ExchangeT(ref array[extremumIndex], ref array[i]);MHeapifyT(array, extremumIndex, heapSize, comparison);3 构造最大（小）堆。
注意到是自底向上进行构造。
private static void BuildMaxHeap(int[] array)for (int i = array.Length - 2 - 1; i = 0; i--)MaxHeapify(array, i, array.Length);private static void BuildMinHeap(int[] array)for (int i = array.Length - 2 - 1; i = 0; i--)MinHeapify(array, i, array.Length);private static void BuildMHeapT(T[] array, ComparisonT comparison)for (int i = array.Length - 2 - 1; i = 0; i--)MHeapifyT(array, i, array.Length, comparison);4 堆排序算法。
以下分别是对整数数组的升序排序、降序排序以及泛型版本。
注意升序排序构造的是最大堆，而降序排序则是构造的最小堆。
public static void HeapSort(int[] array)BuildMaxHeap(array);for (int i = array.Length - 1; i 0; i--)Exchange(ref array[i], ref array[0]);MaxHeapify(array, 0, i);public static void HeapDesSort(int[] array)BuildMinHeap(array);for (int i = array.Length - 1; i 0; i--)Exchange(ref array[i], ref array[0]);MinHeapify(array, 0, i);public static void HeapSortT(T[] array, ComparisonT comparison)BuildMHeapT(array, comparison);for (int i = array.Length - 1; i 0; i--)Exchange(ref array[i], ref array[0]);MHeapifyT(array, 0, i, comparison);三另一种代码的组织方式上述的代码是一种常规的堆排序的实现方式。
但既然是用C#来实现堆排序，应当尽可能的考虑面向对象的方式去实现算法。
考虑到上述代码中，无论是求节点的子节点、父节点、维护最大（小）堆、建立最大（小）堆等方法，本身是属于对堆这种数据结构本身的操作。
因此，可以考虑将其封装成一个数据结构类，在类中进行相关的排序操作。
如下所示：public class HeapT#region Fieldsprivate int _heapSize = 0;private T[] _array = null;#endregion#region Propertiespublic int HeapSizeget { return _heapSize; }set { _heapSize = value; }#endregion#region Constructorspublic Heap(T[] array, int heapSize)_array = array;if(heapSize array.Length)Exception ex = new Exception("The heap size is larger than the array length");throw (ex);_heapSize = heapSize;public Heap(T[] array)_array = array;_heapSize = array.Length;#endregion#region Methodsprivate int Parrent(int index)return (index - 1) - 2;private int Left(int index)return 2 * index + 1;private int Right(int index)return 2 * index + 2;private void MHeapify(int rootIndex, ComparisonT comparison)int leftChildIndex = Left(rootIndex);int rightChildIndex = Right(rootIndex);int extremumIndex = rootIndex;if (leftChildIndex _heapSize comparison(_array[leftChildIndex], _array[rootIndex]) 0)extremumIndex = leftChildIndex;if (rightChildIndex _heapSize comparison(_array[rightChildIndex], _array[extremumIndex]) 0)extremumIndex = rightChildIndex;if (extremumIndex != rootIndex)Helper.ExchangeT(ref _array[extremumIndex], ref _array[rootIndex]);MHeapify(extremumIndex, comparison);private void BuildMHeap(ComparisonT comparison)for (int i = _array.Length - 2 - 1; i = 0; i--)MHeapify(i, comparison);public void Sort(ComparisonT comparison)BuildMHeap(comparison);for (int i = _array.Length - 1; i 0; i--)Helper.Exchange(ref _array[i], ref _array[0]);_heapSize--;MHeapify(0, comparison);#endregion} public class Helperpublic static void ExchangeT(ref T x, ref T y)T temp = x;四算法分析1 在整个堆排序的过程中，只是在原有的数组里对元素进行操作，只需要常数的额外空间。