堆排序算法（C#实现） - Eric Sun - 博客园
Excerpt
在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储区，是软件系统可以编程的内存区域。本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例堆排序的时间复杂度是O(nlog2n),与快速
在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：
一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。
另一种是垃圾收集存储区，是软件系统可以编程的内存区域。
本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例
堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.
**堆排序
**堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。
大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆
堆与数组的关系
堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ， 右节点在数组中的位置（数组下标）为 i * 2 + 2 。
以上是基本的知识点，具体代码如下所示：
1 | <span> //</span><span>堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span> private </span><span>static </span><span>void</span><span> HeapSortFunction(</span><span>int</span><span>[] array)<br> {<br> </span><span>try</span><span><br> {<br> BuildMaxHeap(array); </span><span>//</span><span>创建大顶推（初始状态看做：整体无序）</span><span><br></span><span> for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>-</span><span>1</span><span>; i </span><span>></span><span>0</span><span>; i</span><span>--</span><span>)<br> {<br> Swap(</span><span>ref</span><span> array[</span><span>0</span><span>], </span><span>ref</span><span> array[i]); </span><span>//</span><span>将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）</span><span><br></span><span> MaxHeapify(array, </span><span>0</span><span>, i); </span><span>//</span><span>重新将无序区调整为大顶堆</span><span><br></span><span> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }<br><br> </span><span>///</span><span><summary></span><span><br> </span><span>///</span><span> 创建大顶推（根节点大于左右子节点）<br> </span><span>///</span><span></summary></span><span><br> </span><span>///</span><span><param name="array"></span><span>待排数组</span><span></param></span><span><br></span><span> private </span><span>static </span><span>void</span><span> BuildMaxHeap(</span><span>int</span><span>[] array)<br> {<br> </span><span>try</span><span><br> {<br> </span><span>//</span><span>根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点</span><span><br></span><span> for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>/</span><span>2</span><span>-</span><span>1</span><span>; i </span><span>>=</span><span>0</span><span>; i</span><span>--</span><span>) </span><span>//</span><span>从最底层的最后一个根节点开始进行大顶推的调整</span><span><br></span><span> {<br> MaxHeapify(array, i, array.Length); </span><span>//</span><span>调整大顶堆</span><span><br></span><span> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }<br><br> </span><span>///</span><span><summary></span><span><br> </span><span>///</span><span> 大顶推的调整过程<br> </span><span>///</span><span></summary></span><span><br> </span><span>///</span><span><param name="array"></span><span>待调整的数组</span><span></param></span><span><br> </span><span>///</span><span><param name="currentIndex"></span><span>待调整元素在数组中的位置（即：根节点）</span><span></param></span><span><br> </span><span>///</span><span><param name="heapSize"></span><span>堆中所有元素的个数</span><span></param></span><span><br></span><span> private </span><span>static </span><span>void</span><span> MaxHeapify(</span><span>int</span><span>[] array, </span><span>int</span><span> currentIndex, </span><span>int</span><span> heapSize)<br> {<br> </span><span>try</span><span><br> {<br> </span><span>int</span><span> left </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>1</span><span>; </span><span>//</span><span>左子节点在数组中的位置</span><span><br></span><span> int</span><span> right </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>2</span><span>; </span><span>//</span><span>右子节点在数组中的位置</span><span><br></span><span> int</span><span> large </span><span>=</span><span> currentIndex; </span><span>//</span><span>记录此根节点、左子节点、右子节点 三者中最大值的位置</span><span><br></span><span><br> </span><span>if</span><span> (left </span><span><</span><span> heapSize </span><span>&&</span><span> array[left] </span><span>></span><span> array[large]) </span><span>//</span><span>与左子节点进行比较</span><span><br></span><span> {<br> large </span><span>=</span><span> left;<br> }<br> </span><span>if</span><span> (right </span><span><</span><span> heapSize </span><span>&&</span><span> array[right] </span><span>></span><span> array[large]) </span><span>//</span><span>与右子节点进行比较</span><span><br></span><span> {<br> large </span><span>=</span><span> right;<br> }<br> </span><span>if</span><span> (currentIndex </span><span>!=</span><span> large) </span><span>//</span><span>如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）</span><span><br></span><span> {<br> Swap(</span><span>ref</span><span> array[currentIndex], </span><span>ref</span><span> array[large]); </span><span>//</span><span>将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）</span><span><br></span><span> MaxHeapify(array, large, heapSize); </span><span>//</span><span>以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整</span><span><br></span><span> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }<br><br> </span><span>///</span><span><summary></span><span><br> </span><span>///</span><span> 交换函数<br> </span><span>///</span><span></summary></span><span><br> </span><span>///</span><span><param name="a"></span><span>元素a</span><span></param></span><span><br> </span><span>///</span><span><param name="b"></span><span>元素b</span><span></param></span><span><br></span><span> private </span><span>static </span><span>void</span><span> Swap(</span><span>ref</span><span>int</span><span> a, </span><span>ref</span><span>int</span><span> b)<br> {<br> </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br> temp </span><span>=</span><span> a;<br> a </span><span>=</span><span> b;<br> b </span><span>=</span><span> temp;<br> }</span> |
