- 相關(guān)推薦
C#排序算法之堆排序
關(guān)于C#排序算法的堆排序具體是怎么樣的呢？下面小編為大家整理了C#排序算法之堆排序，希望能幫到大家！
一、基本概念
堆：這里是指一種數(shù)據(jù)結(jié)構(gòu)，而不是我們?cè)贑#中提到的用于存儲(chǔ)引用類型對(duì)象的地方。它可以被當(dāng)成一棵完全二叉樹。
為了將堆用數(shù)組來(lái)存放，這里對(duì)每個(gè)節(jié)點(diǎn)標(biāo)上順序。事實(shí)上，我們可以用簡(jiǎn)單的計(jì)算公式得出父節(jié)點(diǎn)，左孩子，右孩子的索引：
parent(i) =
left(i) = 2i
right(i)=2i + 1
最大堆和最小堆: 最大堆是指所有父節(jié)點(diǎn)的值都大于其孩子節(jié)點(diǎn)的堆，即滿足以下公式：
A[parent[i]]
A[i](A是指存放該堆的數(shù)組)
最小堆相反。
最大堆和最小堆是堆排序的關(guān)鍵，可知最大堆的根節(jié)點(diǎn)是堆中最大的節(jié)點(diǎn)。因此只要我們構(gòu)造出最大(小)堆，最大(小)的元素也就得到了，然后再對(duì)剩下的元素繼續(xù)構(gòu)造最大(小)堆，就可以取出第二大(小)的元素，依此類推，直到排序完成。
二、構(gòu)造最大(小)堆
我們已經(jīng)得知構(gòu)造最大(小)堆是堆排序的關(guān)鍵，下面就來(lái)看看如何構(gòu)造最大堆。
萬(wàn)事開頭難，首先來(lái)看一種特殊的情形吧：堆的根節(jié)點(diǎn)的左子樹和右子樹都已經(jīng)是最大堆了，然而根節(jié)點(diǎn)卻比孩子節(jié)點(diǎn)小，當(dāng)然，這個(gè)堆不滿足最大堆的定義。為了⑩這個(gè)堆成為最大堆，我們可以按如下步驟操作：
�。�1）將根節(jié)點(diǎn)與左右孩子中最大的交換
�。�2）交換之后可能會(huì)面臨左或右子樹不是最大堆的問題，但由于整個(gè)左(右)子樹一開始就是最大堆，問題又回到了最開始的狀態(tài)，因此只要如此反復(fù)即可得到最大堆。
對(duì)于上面的特殊堆已經(jīng)找到了解決辦法，但對(duì)于一般意義上的堆呢？
我們可以選擇自底向上來(lái)構(gòu)造：葉子節(jié)點(diǎn)是特殊的最大堆，舉個(gè)例子有葉子節(jié)點(diǎn)a,b,它們的父節(jié)點(diǎn)是p;a,b肯定已經(jīng)是最大堆了，這是要保證a,b,p組成的子樹是最大堆。這個(gè)堆很眼熟是不是？沒錯(cuò)，它就是前面提到的特殊的堆。在a,b,p組成的子樹變成最大堆后，我們又可以類似的使該子樹，該子樹的父節(jié)點(diǎn)，以及同胞子樹（或節(jié)點(diǎn)）組成的新子樹成為最大堆，如此類推，最終使堆變?yōu)樽畲蠖选?/p>
對(duì)于求解最小堆與此類似。
三、實(shí)現(xiàn)
完整代碼:
復(fù)制代碼 代碼如下:
namespace HeapSort
{
using System;
class Program
{
static int heapSize =0;
static void Main(string[] args)
{
var heap = new[] { -1, 10, 5, 12, 77, 54, 7, 34, 23, 11 };//為了方便，索引0處不存放元素（或存放無(wú)用元素）
heapSize = heap.Length - 1;
BuildMaxHeap(heap);
for (var i = heap.Length - 1; i >= 2; i--)
{
//1.每次在構(gòu)建好最大堆后，將第一個(gè)元素和最后一個(gè)元素交換；
//2.第一次以索引1到length-1出的元素組成新的堆，第二次1到length-2，直到剩下最后兩個(gè)元素組成堆
//3.每次新組成的堆除了根節(jié)點(diǎn)其他節(jié)點(diǎn)都能保持最大堆的特性，因此只要DoBuildMaxHeap(heap, 1)就可以得到新的最大堆
Swap(heap, 1, i);
heapSize--;
MaxHeapfy(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 MaxHeapfy(int[] heap, int index)
{
var largerItemIndex = index;
var leftChildIndex = index << 1;
var rightChildIndex = (index<<1) + 1;
if (leftChildIndex <= heapsize=""> heap[index])
{
largerItemIndex = rightChildIndex;
}
if( index != largerItemIndex)
{
Swap(heap, index, largerItemIndex);
MaxHeapfy(heap, largerItemIndex);
}
}
static void Swap(int[] heap, int index1, int index2)
{
var temp = heap[index1];
heap[index1] = heap[index2];
heap[index2] = temp;
}
}
}
1.MaxHeapfy:該方法的前提是index處節(jié)點(diǎn)的左右子樹已經(jīng)是最大堆，最終的目的是使以index處節(jié)點(diǎn)為根的堆成為最大堆
2.BuildMaxHeap：該方法涉及一個(gè)事實(shí)：如果一個(gè)對(duì)含n個(gè)元素，那么從
開始的元素（假設(shè)節(jié)點(diǎn)下表從1開始）就一定是葉子節(jié)點(diǎn)（這一點(diǎn)可以用反證法證明，假設(shè)
處節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么該節(jié)點(diǎn)必包含子節(jié)點(diǎn)，從而可以得出其左孩子的索引2 *(
) > n的結(jié)論，顯然這是錯(cuò)誤的）。在這個(gè)前提下，該方法至底向上通過MaxHeapfy將堆構(gòu)建成最大堆。
【C#排序算法之堆排序】相關(guān)文章：
java堆排序的算法思想的分析09-14
Java排序算法06-17
PHP快速排序算法詳解08-30
java常見的排序算法的代碼09-20
PHP排序算法類講解07-18
PHP快速排序算法解析10-09
C#實(shí)現(xiàn)協(xié)同過濾算法的實(shí)例代碼06-19
C語(yǔ)言冒泡排序算法實(shí)例06-15