堆练习——堆排序

堆排序，先将数组中存入的数据实现小顶堆的性质，然后再进行一个个的输出排序。

本来堆就是一个数组，是个一维的结构，用数组的下标进行标识。0就是堆的顶，然后把一个数组给维护成一个堆。堆的操作都是原地的。

//堆做堆排序
#include <iostream>

//交换两个数字
void swap(int &a,int &b)
{
    int t;
    t = a;a = b; b = t;
    return;
}
//对数组建堆
void buildheap(int data[],int length,int root,int flag,int num)
{
    if(flag ==1) //对于建完堆之后，排序的调用，需要把ok的排除出去，不再加入维护堆的工作中
        length = num; 
    int left=2*root+1;  
    int right = left+1;
    int min = 0;
    while(left<length)
    {
        if(right<length)
        {
            if(data[root]<=data[left] && data[root]<=data[right])
                break;
            if(data[left]>=data[right])
                min = right;
            else
                 min = left;
            swap(data[root],data[min]);
            buildheap(data,length,min,flag,num);
        }
        else //只有left的时候
        {
            if(data[root]<=data[left])
                break;
            min = left;
            swap(data[root],data[min]);
        }
    }
    return;
}
void heapsort(int data[],int length)
{
    for(int i = length/2-1;i>=0;i--)
    {
        buildheap(data,length,i,0,length);
    }
    int okjiexian = length-1;
    for(okjiexian;okjiexian>=0;okjiexian--)
    {
        swap(data[okjiexian],data[0]);
        buildheap(data,length,0,1,okjiexian);
    } 
    
    return ;
}
//int main()
//{
//    int data[10] = {5,99,9,2,6,8,4,1,10,40};
//    int length = 10;
//    heapsort(data,length);
//    //降序
//    for(int i = 0;i<length;i++)
//        printf("%d\n",data[i]); 
//    return 0;
//}