算法珠玑--再看堆排序(Heap Sort)的实现

堆排序（Heap Sort）堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录.

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1），
它是不稳定的排序方法。

如果需求是从很大的数据中选取特定的几个最大活最小值，那么堆排序是最好的选择。

堆排序的基本步骤就是：

1.初始建堆

2.将堆顶元素与有序区的第一个元素交换

3.然后对堆顶元素开始调整堆，跳转到2执行。直到全部有序。

声明：下面算法的实现中，数组的存储位于data[1]-------data[n]

该算法中最核心的算法是堆的调整算法：

[cpp]
//堆调整
//data[],要排序的数组
//target,要调整的元素位置
//n,数组大小
void AdjustHeap(int data[],int target,int n)
{
    int nChild;
    int nTemp;

    nTemp = data[target];//暂存
    while(target * 2 <= n)
    {
        nChild = target * 2;//nChild指向左孩子
        if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
        {
            nChild++;//nChild指向关键字大的孩子（看是否有左孩子，若有，则左右孩子比较）
        }
        if(nTemp < data[nChild])//孩子节点比父节点大，则进行孩子节点移到父节点的位置
        {
            data[target] = data[nChild];
            target = nChild;//再处理刚刚调整过的节点的字节点
        }
        else break;
    }
    data[target] = nTemp;//最后将要调整的元素放到合适的位置
}

//堆调整
//data[],要排序的数组
//target,要调整的元素位置
//n,数组大小
void AdjustHeap(int data[],int target,int n)
{
int nChild;
int nTemp;

nTemp = data[target];//暂存
while(target * 2 <= n)
{
  nChild = target * 2;//nChild指向左孩子
  if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
  {
   nChild++;//nChild指向关键字大的孩子（看是否有左孩子，若有，则左右孩子比较）
  }
  if(nTemp < data[nChild])//孩子节点比父节点大，则进行孩子节点移到父节点的位置
  {
   data[target] = data[nChild];
   target = nChild;//再处理刚刚调整过的节点的字节点
  }
  else break;
}
data[target] = nTemp;//最后将要调整的元素放到合适的位置
}
整体实现代码：

[cpp]
****************
* 堆排序算法
* 排序数组下标从1开始
*/
#include <stdio.h>

enum{MAX = 1000+1,};

int data[MAX];
static inline swap(int x,int y)
{/*
    x ^= y;
    y ^= x;
    x ^= y;
    */
    int tmp;
    tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
}
//堆调整
//data[],要排序的数组
//target,要调整的元素位置
//n,数组大小
void AdjustHeap(int data[],int target,int n)
{
    int nChild;
    int nTemp;

    nTemp = data[target];//暂存
    while(target * 2 <= n)
    {
        nChild = target * 2;
        if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
        {
            nChild++;//nChild指向关键字大的孩子
        }
        if(nTemp < data[nChild])
        {
            data[target] = data[nChild];
            target = nChild;//再处理刚刚调整过的节点的字节点
        }
        else break;
    }
    data[target] = nTemp;//最后将要调整的元素放到合适的位置
}

//堆排序算法
//data，要排序的数组
//n，数组大小
void HeapSort(int data[],int n)
{
    int i;
    //初始建堆
    for(i = n/2;i > 0;--i)
    {
        AdjustHeap(data,i,n);
    }
    //每次循环将堆顶元素与有序区第一个元素交换，然后再调整堆
    for(i = n;i > 1;--i)
    {
        swap(1,i);
        AdjustHeap(data,1,i - 1);
    }
}

int main()
{
    freopen("random","r",stdin);
    freopen("oder","w",stdout);
    int i;
    for(i = 1;i <= MAX;++i)
    {
        scanf("%d",&data[i]);
    }
    //stderr("开始排序\n");
    HeapSort(data,MAX);
    //stderr("排序结束\n");
    for(i = 1;i <= MAX;++i)
    {
        printf("%d\n",data[i]);
    }
    return 0;
}

/****************
* 堆排序算法
* 排序数组下标从1开始
*/
#include <stdio.h>

enum{MAX = 1000+1,};

int data[MAX];
static inline swap(int x,int y)
{/*
x ^= y;
y ^= x;
x ^= y;
*/
int tmp;
tmp = data[x];
data[x] = data[y];
data[y] = tmp;
}
//堆调整
//d

补充：软件开发 , C++ ,