因为是大顶堆, 所以根节点肯定是最大值了, 把根节点和最后一个结点进行交换, 就认为第一趟堆排序完成.然后除97这个序列再进行堆排序, 如此反复直到有序为止.

   来看下代码实现:

///< 大顶堆调整
void HeapAdjust(int ziArray[], int iNonLeafIndex, int iLen)  {
     
    int iLeftChild = 2*iNonLeafIndex + 1;   
    int iRightChild = 2*iNonLeafIndex + 2;  
    int iMaxChild = iLeftChild;
    while (iLeftChild < iLen) {
        if (iRightChild < iLen) { ///< 说明有右儿子结点
            if (ziArray[iLeftChild]<ziArray[iRightChild]) {
                iMaxChild = iRightChild; ///< 算出最大儿子结点Index
            }
        }
        if (ziArray[iNonLeafIndex] < ziArray[iMaxChild]) {
            int iTemp = ziArray[iNonLeafIndex];
            ziArray[iNonLeafIndex] = ziArray[iMaxChild];
            ziArray[iMaxChild] = iTemp;
 
            iNonLeafIndex = iMaxChild;
            iLeftChild = 2*iNonLeafIndex + 1;  
            iRightChild = 2*iNonLeafIndex + 2; 
            iMaxChild = iLeftChild;
 
        } else {
            break;
        }
    }
    int i = 0;
    for(; i<iLen; i++)   {   
        printf("%d ", ziArray[i]);
    }
    printf("\n");
    return;   
}   
 
void HeapSort(int ziArray[], int iLen) {   
    int i=0;   
    ///< 建立初始堆 
    for (i=iLen/2; i>=1; i--) {   
        printf("从非叶结点%d调整:", i);
        HeapAdjust(ziArray, i-1, iLen);    ///< 从0开始 
    }
 
    printf("\n%s\n", "递归调整过程:");
    for (i=iLen-1; i>0; i--) {  
        printf("取出本次调整的根结点:%d--", ziArray[0]);
        ///<交换根结点和最后一个结点 
        int temp =ziArray[0];   
        ziArray[0] = ziArray[i];   
        ziArray[i] = temp;   
        HeapAdjust(ziArray, 0, i);   
    }   
    return;   
}   
 
int main()   
{   
    int ziArray[] ={49,38,65,97,76,13,27,49};   
 
    int iLen = sizeof(ziArray)/sizeof(int);
    printf("%s\n", "原序列:");
    int i = 0;
    for(; i<iLen; i++)   {   
        printf("%d ", ziArray[i]);
    }
    printf("\n");
    HeapSort(ziArray, 8);   
    printf("最后结果:");
    for(i=0; i<8; i++)   {   
        printf("%d ", ziArray[i]);
    }   
 
    return 0;   
} 

   实现结果为:

原序列:
49 38 65 97 76 13 27 49
从非叶结点4调整:49 38 65 97 76 13 27 49
从非叶结点3调整:49 38 65 97 76 13 27 49
从非叶结点2调整:49 97 65 49 76 13 27 38
从非叶结点1调整:97 76 65 49 49 13 27 38
 
递归调整过程:
取出本次调整的根结点:97--76 49 65 38 49 13 27
取出本次调整的根结点:76--65 49 27 38 49 13
取出本次调整的根结点:65--49 49 27 38 13
取出本次调整的根结点:49--49 38 27 13
取出本次调整的根结点:49--38 13 27
取出本次调整的根结点:38--27 13
取出本次调整的根结点:27--13
最后结果:13 27 38 49 49 65 76 97

   堆排序的时间复杂度是和完全二叉树的高度有关的. 完全二叉树的高度为O(log_2(n+1)),即结点最坏的调整堆的时间为O(log_2n),另外在调整堆的过程中, 完全二叉树从最下层最右边的非终端结点开始调整, 将它与其孩子进行比较和交换, 对于每个非终端结点来说，其实最多进行两次比较和交换操作，因此整个调整堆的最坏时间复杂度为O(n).所以最坏时间复杂度为O(nlog_2n).

   堆排序空间复杂度为O(1), 因为需要一个临时变量存储中间数据.快排的时间复杂度为O(nlog_2n),但是它的空间复杂度也为O(nlog_2n),而堆排序是O(1), 这个是堆排序的优势.