堆排序

// 堆排序.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
//将L数组中s到len的数据建立成为大顶堆
void HeapAdjust(int *L,int s,int len)
{
    int  temp;
    temp=L[s];
    for(int j=2*s;j<=len;j=j*2)
    {
        if(j<len&&L[j]<=L[j+1])//找到孩子节点中较大的那个
        {
            j++;
        }
        if(temp<L[j])//如果节点比孩子节点中较大的那个小，将此节点替换为较大的孩子节点
        {
            L[s]=L[j];
            s=j;
        }
    }
    L[s]=temp;
}
void swap(int *L,int i,int j)
{
    int temp=L[i];
    L[i]=L[j];
    L[j]=temp;
}
//输入数组名和数组长度，进行堆排序
void heapsort(int *L,int len)
{
    //从最后一个含有叶子节点的节点开始构造堆（参见二叉树性质5）
    for(int i=len/2;i>0;i--)
    {
        HeapAdjust(L,i,len);
    }
    //每一次交换堆顶和堆尾元素，然后重新构造堆
    for(int i=len;i>1;i--)
    {
        swap(L,1,i);
        HeapAdjust(L,1,i-1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int num[10]={0,2,5,4,7,5,4,8,41,86};
    //注意这里由于堆排序利用的是二叉树的第五条性质，所以数组下标要从1开始，num中0不在排序的序列之中
    heapsort(num,9);
    for(int i=1;i<10;i++)
    {
        cout<<num[i]<<' ';
    }
    return 0;
}