선수 권 대회 정렬 과 쌓 기 정렬

1964 년 에 쌓 인 순 서 는 선수 권 대회 순위 의 여러 가지 단점 을 개선 했다.
선수 권 대회 정렬:
선수 권 대회 순 위 는 트 리 선택 정렬 (Tree Selection Sort) 이 라 고도 부 르 며 선수 권 대회 의 사상 에 따라 순 위 를 매 기 는 방법 이다.
먼저 n 개의 기록 을 두 가지 로 비교 한 다음 에 우승자 간 에 두 가지 비 교 를 한 다음 에 최소 키 워드 를 선택 할 때 까지 반복 합 니 다.이 과정 은 n 개의 잎 결점 이 있 는 완전 이 진 트 리 로 표시 할 수 있다.뿌리 노드 의 키 워드 는 바로 잎 결점 중의 가장 작은 키워드 이다.최소 키 워드 를 출력 한 후에 관계 의 전달 가능성 에 따라 다음 의 작은 키 워드 를 선택 하려 면 잎 결점 중의 최소 키 워드 를 '최대 치' 로 바 꾸 어야 한다. 예 를 들 어 표시 한 다음 에 이 잎 결점 부터 왼쪽 (오른쪽) 형제의 키워드 와 비교 하여 잎 결점 에서 뿌리 까지 의 경로 에서 각 결점 의 키 워드 를 수정 해 야 한다.뿌리 결점 의 키 워드 는 바로 차 소 키워드 이다.
이런 알고리즘 의 단점 은 보조 저장 공간 이 비교적 많 고 최대 값 을 불필요 하 게 비교 하 는 것 이다.
이런 단점 을 보완 하기 위해 1964 년, 쌓 기 서열 이 탄생 했다.
　　
더미 정렬:
쌓 기 정렬 (Heap Sort) 은 크기 를 기록 하 는 보조 공간 만 필요 합 니 다.
쌓 기 정렬 의 정 의 는 다음 과 같다. n 개 요소 의 서열 은 '모든 비 터미널 노드 의 값 이 같 거나 작 거나 같 음' 을 만족 시 키 면 아이의 값 을 좌우 한다. ”이 를 더미 라 고 합 니 다. 만약 서열 {k1, k2,..., kn} 이 더미 라면, 더미 꼭대기 요소 (즉, 완전 이 진 트 리 의 뿌리) 는 서열 중 n 개 요소 의 최소 값 (또는 최대 값) 이 어야 합 니 다. 。
출력 더미 꼭대기 의 최소 값 을 출력 한 후에 나머지 n - 1 개 요소 의 서열 을 다시 쌓 으 면 n 개 요소 중의 작은 값 을 얻 을 수 있 습 니 다. 이렇게 반복 적 으로 실행 하면 질서 있 는 서열 을 얻 을 수 있 습 니 다. 이 과정 을 쌓 기 정렬 이 라 고 합 니 다.
지금까지 쌓 기 순 서 를 실현 하려 면 두 가지 문 제 를 해결 해 야 한다.
(1) 어떻게 무질서 한 서열 로 무 더 기 를 만 듭 니까?
(2) 어떻게 출력 더미 요 소 를 출력 한 후에 나머지 요 소 를 조정 하여 새로운 더미 가 됩 니까? 
문제 1 의 해결 방법 은? ：무질서 한 서열 로 쌓 아 올 리 는 과정 은 '선별' 을 반복 하 는 과정 입 니 다. 이 서열 을 완전 이 진 트 리 로 보면 마지막 비 터미널 노드 는 n / 2 번 요소 입 니 다. 이 를 통 해 '선별' 은 n / 2 번 요소 부터 시작 합 니 다.
쌓 기 정렬 방법 은 기록 수가 비교적 적은 파일 에 대해 제창 할 가치 가 없 지만 n 이 비교적 큰 파일 에 효과 가 있다.
문제 2 의 해결 방법 은?
 ：더미 요 소 를 출력 한 후에 더미 의 마지막 요소 로 대체 합 니 다. 이때 뿌리 결산 점 의 왼쪽, 오른쪽 나 무 는 모두 더미 이 고 위 에서 아래로 조정 하면 됩 니 다. 우 리 는 꼭대기 에서 잎 까지 의 조정 과정 을 '라 고 부 릅 니 다.
선별 하 다
 ”。
쌓 기 정렬 이 최 악의 경우 시간 복잡 도 는 O (nlogn) 로 빠 른 정렬 에 비해 쌓 기 정렬 의 가장 큰 장점 이다.
정렬 소스 코드 쌓 기:

#include <fstream>
#include <iostream>
using namespace std;


void Exchange( int * p, int * q){
	int t = *p;
	*p=*q;
	*q=t;
}


int Left( int i ){
	return i*2+1;
}


int Right( int i){
	return i*2+2;
}


//void MaxHeaplify(int *data, int len, int i)
//{
//    int L = Left(i);
//    int R = Right(i);
//    int largest = 0;
//    if (L < len && data[L] > data[i])
//    {
//        largest = L;
//    }
//    else
//    {
//        largest = i;
//    }
//    if (R < len && data[R] > data[largest])
//    {
//        largest = R;
//    }
//    if (largest != i)
//    {
//        Exchange(data + i, data + largest);
//        MaxHeaplify(data, len, largest);
//    }
//}


void MaxHeaplify( int * data, int len, int i){
	int L = Left( i );
	int R = Right( i);
	int largest = i;
	if( L<len )
		largest= data[L]>data[i]?L:i;
	if( R<len )
		largest = data[largest]>data[R]?largest:R;
	if(largest!=i){
		Exchange(data+i, data+largest);
		MaxHeaplify( data, len, largest);
	}
}




void BuildHeap( int * data, int len ){
	for( int i=len/2-1; i>=0; i--)
		MaxHeaplify( data, len, i);
}


void HeapSort( int * data, int len ){
	BuildHeap( data, len);
	for( int i=len-1; i>=0; i--){
		Exchange( data+i,data);
		len--;
		MaxHeaplify( data,len,0);
	}
}


void OutputArray( int * data, int len){
	for( int i=0; i<len; i++){
		cout << data[i] <<" ";
	}
	cout << endl;
}


int main()
{
	int data[9] = {7,5,3,4,9,0,3,6,8};
	//int data[3] ={5,8,4};
	HeapSort(data, 9);
	OutputArray(data, 9);
    return 0;
}