堆排序(大顶堆)_非递减序列

堆的定义: 如下,n个元素的序列{k₁ ,k₂ ,...k_n }当且仅当满足下关系时,称之为堆.

k_i <= k_2i ;k_i <= k_2i+1 (小顶堆) 或者 k_i >= k_2i ;k_i >= k_2i+1 (大顶堆)

堆排序 :建大顶堆,使堆顶元素与堆中最后一个元素替代之(放置数组尾,数组尾为当前最大元素).,

堆的剩余未排序的元素,建大顶堆,重复上述过程.

#include <stdio.h>
//已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。
//按此思想写一个从空堆开始一个一个填入元素的建堆算法
//（题示：增加一个k n+1后应从叶子向根的方向调整）
#define length 6
void HeadSort(int a[],int n);
void HeadAdjust(int a[],int s, int m);
void HeadAdjust(int *a,int head, int tail) {   
    int temp;
    temp = a[head];           //若s=2 ,则rc = a[1]
    for ( int j= 2*head; j <= tail; j= 2*j) {
        if( j<tail && a[j]<a[j+1])
            ++j;
        if( temp > a[j])   
            break;
        a[head] = a[j];
        head = j;           
    }
    a[head] = temp;   
//打印*********************
    for(int i = 0 ; i < length; i++) {
            printf("%d ",a[i]);
    }
    printf("/r/n");
   
//打印*********************打印结束
} //    HeadAdjust
void HeadSort(int *a,int n) {
    int i;
    int tmp;
    for( i = length/2  ; i > 0; --i) {
        HeadAdjust(a,i,length);
    }
//打印*********************
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//**********************打印结束
    tmp = a[0];
    a[0] = a[length-1];
    a[length-1] = tmp;
//打印**********************   
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//打印*********************打印结束
    for(i = length-1; i>1; --i) {//////////////
        printf("i's value:%d/n",i);
        HeadAdjust(a,0,i);
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;   
    }
    printf("i's value:%d/n",i);
}
int main() {
   
    int n ; 
    int a[1000] ;
    printf("Input the Number you want to Sort :");
    scanf("%d",&n);
    printf("Please Input the values :");
    for(int i=0;i<n;++i) 
        scanf("%d",&a[i]);//输入时,不能在"%d"内多出任何空格,否则需要多敲一个字符********************Important
    printf("/r/n");
    HeadSort(a,n);
    for(i=0;i<n;++i) 
        printf("%d ",a[i]);
    printf("/r/n");
    return fals