9 도 OJ 1202 정렬 - 쌓 기 정렬

제목 주소:http://ac.jobdu.com/problem.php?pid=1202
제목 설명:
    입력 한 n 개 수 를 정렬 하고 출력 합 니 다.
입력:
    입력 한 첫 줄 은 정수 n (1 < = n < = 100) 을 포함 합 니 다.    다음 줄 은 n 개의 정 수 를 포함한다.
출력:
    여러 그룹의 테스트 데이터 가 있 을 수 있 습 니 다. 각 그룹의 데이터 에 대해 정렬 된 n 개의 정 수 를 출력 하고 각 수의 뒤에 빈 칸 이 있 습 니 다.    각 그룹의 테스트 데이터 결과 가 한 줄 을 차지한다.
샘플 입력:

4
1 4 3 2

샘플 출력:

1 2 3 4 

#include <stdio.h>
#include <stdlib.h>
 
void HeapSort(int Array[], int len);
void BuildMaxHeap(int Array[], int len);
void ShiftDown(int Array[], int index, int len);
void Swap(int *m, int *n);
 
int main(void){
    int len;
    int * Array;
    int i;
 
    while (scanf("%d", &len) != EOF){                 //      
        Array = (int *)malloc(sizeof(int) * (len+1));
        for (i=1; i<=len; ++i)             //    
            scanf("%d", &Array[i]);
 
        BuildMaxHeap(Array, len);
        HeapSort(Array, len);
        for (i=1; i<=len; ++i)
            printf("%d ", Array[i]);
        printf("
");
        free(Array);
    }
    return 0;
}
 
void HeapSort(int Array[], int len){
    int i;
    int time = len;
    for (i=0; i<len; ++i){
        Swap(&Array[1], &Array[time]);
        --time;
        ShiftDown(Array, 1, time);
    }
}
 
void BuildMaxHeap(int Array[], int len){
    int index = len/2;
 
    for (; index>0; --index){
        ShiftDown(Array, index, len);
    }
}
void ShiftDown(int Array[], int index, int len){
    while ((2*index) <= len || (2*index+1) <= len){
        if (2*index+1 <= len){
            if (Array[index] < Array[2*index] ||
                Array[index] < Array[2*index+1]){
                if (Array[2*index] > Array[2*index+1]){
                    Swap(&Array[index], &Array[2*index]);
                    index = 2*index;
                }
                else{
                    Swap(&Array[index], &Array[2*index+1]);
                    index = 2*index + 1;
                }
            }
            else
                break;
        }
        else{
            if (Array[index] < Array[2*index]){
                Swap(&Array[index], &Array[2*index]);
                index = 2*index;
            }
            else
                break;
        }
    }
}
 
void Swap(int *m, int *n){             //    
    int tmp;
    tmp = *m;
    *m = *n;
    *n = tmp;
}

참고 자료:http://blog.csdn.net/v_july_v/article/details/6198644