资源描述：
《c# 排序算法之堆排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、C#排序算法之堆排序这里是指一种数据结构，而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。一、基本概念堆：这里是指一种数据结构，而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。为了将堆用数组来存放，这里对每个节点标上顺序。事实上，我们可以用简单的计算公式得出父节点，左孩子，右孩子的索引：parent(i)=left(i)=2iright(i)=2i+1最大堆和最小堆:最大堆是指所有父节点的值都大于其孩子节点的堆，即满足以下公式：A[parent[i]]
2、A[i](A是指存放该堆的数组)最小堆相反。最大堆和最小堆是堆排序的关键，可知最大堆的根节点是堆中最大的节点。因此只要我们构造出最大(小)堆，最大(小)的元素也就得到了，然后再对剩下的元素继续构造最大(小)堆，就可以取出第二大(小)的元素，依此类推，直到排序完成。二、构造最大(小)堆我们已经得知构造最大(小)堆是堆排序的关键，下面就来看看如何构造最大堆。万事开头难，首先来看一种特殊的情形吧：堆的根节点的左子树和右子树都已经是最大堆了，然而根节点却比孩子节点小，当然，这个堆不满足最大堆的定义。为了⑩这个堆成为最大堆，
3、我们可以按如下步骤操作：（1）将根节点与左右孩子中最大的交换（2）交换之后可能会面临左或右子树不是最大堆的问题，但由于整个左(右)子树一开始就是最大堆，问题又回到了最开始的状态，因此只要如此反复即可得到最大堆。对于上面的特殊堆已经找到了解决办法，但对于一般意义上的堆呢？我们可以选择自底向上来构造：叶子节点是特殊的最大堆，举个例子有叶子节点a,b,它们的父节点是p;a,b肯定已经是最大堆了，这是要保证a,b,p组成的子树是最大堆。这个堆很眼熟是不是？没错，它就是前面提到的特殊的堆。在a,b,p组成的子树变成最大堆后，
4、我们又可以类似的使该子树，该子树的父节点，以及同胞子树（或节点）组成的新子树成为最大堆，如此类推，最终使堆变为最大堆。对于求解最小堆与此类似。三、实现完整代码:复制代码代码如下:namespaceHeapSort{usingSystem;classProgram{staticintheapSize=0;staticvoidMain(string[]args){varheap=new[]{-1,10,5,12,77,54,7,34,23,11};//为了方便，索引0处不存放元素（或存放无用元素）heapSize=he
5、ap.Length-1;BuildMaxHeap(heap);for(vari=heap.Length-1;i>=2;i--){//1.每次在构建好最大堆后，将第一个元素和最后一个元素交换；//2.第一次以索引1到length-1出的元素组成新的堆，第二次1到length-2，直到剩下最后两个元素组成堆//3.每次新组成的堆除了根节点其他节点都能保持最大堆的特性，因此只要DoBuildMaxHeap(heap,1)就可以得到新的最大堆Swap(heap,1,i);heapSize--;MaxHeapfy(heap,
6、1);}foreach(variinheap)Console.Write(i+"");}staticvoidBuildMaxHeap(int[]heap){for(vari=(heap.Length-1)/2;i>=1;i--){MaxHeapfy(heap,i);}}staticvoidMaxHeapfy(int[]heap,intindex){varlargerItemIndex=index;varleftChildIndex=index<<1;varrightChildIndex=(index<<1)+1;i
7、f(leftChildIndex<=heapSize&&heap[leftChildIndex]>heap[index]){largerItemIndex=leftChildIndex;}if(rightChildIndex<=heapSize&&heap[rightChildIndex]>heap[largerItemIndex]){largerItemIndex=rightChildIndex;}if(index!=largerItemIndex){Swap(heap,index,largerItemIndex
8、);MaxHeapfy(heap,largerItemIndex);}}staticvoidSwap(int[]heap,intindex1,intindex2){vartemp=heap[index1];heap[index1]=heap[index2];heap[index2]=temp;}}}1.MaxHeapfy:该方法的前提是index处节点的左右
