heap sort

堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)，

它是不稳定的排序方法。

//heap sort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void print(int *str, int len)
{
    int i=1;
    printf("==> str: ");
    while(i<=len)
        printf("%d ", str[i++]);
    printf("\n");
}

void heapify(int *str, int low,int high)
{
    //筛选法调整堆

    int large;
    int temp;
    temp = str[low];
    for(large=2*low; large<=high; large*=2){
        if( (large<high) && (str[large]<str[large+1]) )
            large++;
        if (temp >= str[large]) break;
        str[low] = str[large];
        low = large;
    }
    str[low] = temp;
}

void buildheap(int *str, int len)
{//建堆

    int i;
    for (i=len/2; i>0; i--)
        heapify(str, i, len);
}


//堆排序

void HeapSort(int *str, int len)
{
    int i;
    buildheap(str, len); //建大根堆


    for (i=len; i>1; i--){
        str[0]=str[1]; str[1]=str[i]; str[i]=str[0];
        //将根结点与堆的最后一个结点交换位置

        heapify(str, 1, i-1);//自根而下调整堆

    }
}


int main(void)
{
    int len;
    int a[20];
    int i;

    while(1){
        printf("input string length: ");
        scanf(" %d", &len);
        fflush(stdin);
        if(len == 0) break;
        //设置rand函数所用的启始种子值，以期每次产生的随机数序列均不相同。

        srand(time(NULL));
        i = 0;
        while(i++ < len){//a[0] 为哨岗

            a[i] = rand() % 100;
            printf("%d ", a[i]);
        }
        putchar('\n');
        //a[1] = 93; a[2] = 56; a[3] = 43; a[4] = 40;

        //a[5] = ; a[6] = ; a[7] = ; a[8] = ;

        //a[9] = ; a[10] = ;

    
        HeapSort(a, len);
        
        i=1;
        while(i<=len)
            printf("%d ", a[i++]);
        printf("\n");
    
    }//while(1)

    
    return 0;
}