堆排序及C语言实现

排序系列之（2）
堆排序是利用一直特殊的数据结构来完成排序工作的，即“堆”。堆可以被看做一棵完全二叉树，树的每一层都会填满，最后一层可能除外。这种堆有两种：最大堆和最小堆。在堆排序算法中，使用的是最大堆。最小堆通常在构造优先队列时使用。最大堆的性质是除了根节点之外的每一个节点，其父节点的值必须大于等于其子节点。即t[parent] >= t[child]

以下是其源代码实现

view plaincopy to clipboardprint?
/************************************************
* 测试从数组0号位开始的堆排序
*
* 与上面不同的知识点
* 1.0号是根元素，则左孩子为2i+1,右孩子为2(i+1);
* 2.孩子为i，则父亲为i-1/2
*
*/
/**
* a: 待排序数组
* len: 数组长度
*/
void heapSort2(int a[],int len)
{
int i=0;
int maxHeapIndex = len-1;
//首先建堆
for(i=(maxHeapIndex-1)/2;i>=0;i--)
{
maxHeapify2(a,i,maxHeapIndex);
}
for(i=maxHeapIndex;i>=1;i--)
{
swap(&a[0],&a[i]);
// 交换之后，继续堆化时，堆数组最大索引要减1
maxHeapify2(a,0,i-1);
}
}
/***
* a 待排数组
* rootIndex 本次堆化的跟
* maxHeapIndex 本次堆化所达到的堆数组最大索引
*/
void maxHeapify2(int a[], int rootIndex,int maxHeapIndex)
{
int lChild = rootIndex*2+1;
int rChild = (rootIndex+1)*2;
int largest = rootIndex;
if(lChild <= maxHeapIndex && a[lChild] > a[rootIndex])
largest = lChild;
if(rChild <= maxHeapIndex && a[rChild] > a[largest])
largest = rChild;
if(largest != rootIndex)
{
swap(&a[largest],&a[rootIndex]);
maxHeapify2(a,largest,maxHeapIndex);
}
}
void heapSortTest2()
{
int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
int len = sizeof(a)/sizeof(int);
showArray(a,len);
heapSort2(a,len);
showArray(a,len);
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/taizhoufox/archive/2010/10/13/5938616.aspx