堆排序

堆排序

堆排序思想说起来还不太好组织语言。

它的做法就是，首先将待排序序列组织成一个大（小）顶堆，然后逐次将首元素和最后一个元素交换，序列长度减一后再次调整序列成一个大顶堆。自此就成了一个升（降）序列。

c代码如下：（参考《大话数据结构》）

void HeapAdjust (int * const piSrc, const int startIndex, const int len){    int parentIndex = startIndex;    int maxChildIndex;    int temp;    if (parentIndex < len)    {        temp = piSrc[parentIndex];        while ((parentIndex<len) && (2*parentIndex+1<len))        {            maxChildIndex = 2*parentIndex + 1; // left            if (maxChildIndex+1<len&&piSrc[maxChildIndex+1]>piSrc[maxChildIndex])                maxChildIndex ++; // right child is the max value            if (piSrc[maxChildIndex] > piSrc[parentIndex]) // if child value is greater than parent                piSrc[parentIndex] = piSrc[maxChildIndex]; // parent value = child value            else                break;            parentIndex = maxChildIndex;            piSrc[parentIndex] = temp;        }    }}void HeapSort (int * const piSrc, const int len){    int i;    int temp;    if (NULL != piSrc)    {        for (i=len/2-1; i>=0; i--)            HeapAdjust (piSrc, i, len);        for (i=len-1; i>0; i--)        {            temp = piSrc[i];            piSrc[i] = piSrc[0];            piSrc[0] = temp;            HeapAdjust (piSrc, 0, i);        }    }}
注：
首先将序列调整成一个大顶堆，即每个结点数值都大于或等于左右孩子结点数值。
for (i=len/2-1; i>=0; i--)    HeapAdjust (piSrc, i, len);有左右孩子的结点最大索引即是len/2-1。
在HeapAdjust函数中，以startIndex为开始，逐次向下调整成大顶堆。即：如果左右孩子中最大的值比双亲节点的数值大，交换位置；否则，退出。
完整c代码如下：
#include <stdio.h>#include <stdlib.h>#include<windows.h>void HeapAdjust (int * const piSrc, const int startIndex, const int len){    int parentIndex = startIndex;    int maxChildIndex;    int temp;    if (parentIndex < len)    {        temp = piSrc[parentIndex];        while ((parentIndex<len) && (2*parentIndex+1<len))        {            maxChildIndex = 2*parentIndex + 1; // left            if (maxChildIndex+1<len&&piSrc[maxChildIndex+1]>piSrc[maxChildIndex])                maxChildIndex ++; // right child is the max value            if (piSrc[maxChildIndex] > piSrc[parentIndex]) // if child value is greater than parent                piSrc[parentIndex] = piSrc[maxChildIndex]; // parent value = child value            else                break;            parentIndex = maxChildIndex;            piSrc[parentIndex] = temp;        }    }}void HeapSort (int * const piSrc, const int len){    int i;    int temp;    if (NULL != piSrc)    {        for (i=len/2-1; i>=0; i--)            HeapAdjust (piSrc, i, len);        for (i=len-1; i>0; i--)        {            temp = piSrc[i];            piSrc[i] = piSrc[0];            piSrc[0] = temp;            HeapAdjust (piSrc, 0, i);        }    }}int testArray[] = {1,3,5,7,9,2,4,6,8,0, 54, 48, 2 , 5 , 8};//{5,5,5,5,5,5,5,5,5,5,5};//void PRintfIntArray (int * const pia, const int n){    int i;    for (i=0; i<n; i++)        printf("%u ", pia[i]);    printf("/n");}int main(){    DWord startTime;    DWORD endTime;    printf("Hello world!/n");    startTime = GetTickCount ();    HeapSort (testArray, sizeof(testArray)/sizeof(int));    endTime = GetTickCount();    printf ("Sort Time Consumption:%lu ms./n", endTime-startTime);    PrintfIntArray (testArray, sizeof(testArray)/sizeof(int));    return 0;}