데이터 구조의 더미 정렬 C 언어 구현

쌓 기 정렬: 시간 복잡 도: O (nlogn) 안정성: 불안정 실현 원리: 정렬 을 기다 리 는 서열 을 하나의 큰 쌓 기 (또는 작은 쌓 기) 로 구성 하 는 전체 서열 의 최대 치 는 쌓 기 지붕 의 뿌리 노드 이 고 이 를 옮 기 는 것 이다 (즉, 배열 의 끝 요소 와 교환 하 는 것 이다. 이때 끝 요 소 는 최대 치 이다).그 다음 에 남 은 n - 1 개의 서열 을 하나의 더 미 를 다시 구성 하면 n 개 요소 의 최대 치 를 이렇게 반복 적 으로 집행 하여 질서 있 는 서열 을 얻 을 수 있 습 니 다.큰 지붕 더미: 뿌리 노드 가 가장 큰 작은 지붕 더미: 뿌리 노드 가 가장 작은 큰 지붕 더미 만족 조건: K [i] > = K [2 * i + 1] 그리고 K [2 * i + 1] > K [2 * i + 2] (0 < = i < = i < = n / 2 - 1) K [2 * i + 1] 은 왼쪽 나무 K [2 * i + 2] 를 쌓 아 올 린 오른쪽 나무 작은 지붕 더미 만족 조건: K [i] < = K [2 * i + 1] & K [2 * i + 1] 그리고 K [2 * i + 2] < = K [2 * i + 2] (0 < i < = i < = i < = n / 2 - 1) 실현 절차: 1. 먼저 초기 파일 R [1. n. n] 을 쌓 아 올 리 고 큰 지붕 을 쌓 아 올 리 고, 큰 지붕 을 쌓 아 올이 더 미 는 초기 무질서 구역 2. 키워드 의 가장 큰 기록 R1 과 무질서 구역 의 마지막 기록 R [n] 을 교환 합 니 다. 3. 이 를 통 해 새로운 무질서 구역 R [1. n - 1] 과 질서 구역 R [n] 을 얻 고 R [1. n - 1]. keys ≤ R [n]. key 4 를 만족 시 킵 니 다. 교환 후 새로운 뿌리 R [1] 은 더미 의 성질 을 위반 할 수 있 으 므 로 현재 무질서 구역 R [1. n - 1] 을 더미 로 조정 해 야 합 니 다.5. 그 다음 에 R [1. n - 1] 에서 키워드 가 가장 큰 기록 R [1] 과 이 구간 의 마지막 기록 R [n - 1] 을 교환 하고 6. 이 를 통 해 새로운 무질서 구역 R [1. n - 2] 와 질서 구역 R [n - 1. n] 을 얻 으 며 관계 R [1. n - 2]. keys ≤ R [n - 1. n]. keys, 7. 마찬가지 로 R [1. n - 2] 를 더미 로 조정 해 야 한다.무질서 한 구역 에 하나의 요소 만 있 을 때 까지 큰 배열 로 구축 하 는 기본 작업: 초기 화 작업: R [1. n] 을 초기 로 구성 합 니 다.모든 정렬 의 기본 동작: 현재 무질서 구역 의 더미 기록 R [1] 과 이 구간 의 마지막 기록 을 교환 한 다음 에 새로운 무질서 구역 을 더미 로 조정 합 니 다.작은 지붕 더미 의 구축 은 큰 지붕 더미 와 반대 된다.

//    ：    
#include 
#inlude 
/****************************************************************************
    ：        
      ： int i：           
             2*i+1:  i      
             2*i+2:  i      
             int len:             
   ： 
*******************************************************************************/
void HeapAdjust(int a[],int i,int len)
{
   while( 2*i+1 < len )
   {
      int maxindex=2*i+1; //          s     
      if(2*i+2//         ，      Index  
         if(a[2*i+1]2*i+2])
{
maxindex=2*i+2;
}
}
if(a[i]/ / i 와 max index 의 데이터 교환
a[i]=a[i]^a[maxindex];
a[maxindex]=a[i]^a[maxindex];
a[i]=a[i]^a[maxindex];
/ / 더미 가 파괴 되 어 재 조정 이 필요 합 니 다.
i=maxindex;
}
else
{
/ / 좌우 아이들 이 모두 크 면 파괴 되 지 않 고 조정 이 필요 하지 않 습 니 다.
break;
}
}
return;
}
/ / 더미 정렬
void HeapSort(int a[],int len)
{
int i=0;
/ / a [0, Len - 1] 을 돔 으로 만든다.
for(i=len/2-1;i>=0;i--)
{
/ / 큰 지붕 쌓 기 함수 호출
HeapAdjust(a,i,len);
}
/ / n - 1 번 정렬 만 하면 됩 니 다.
for(i=len-1;i>0;i--)
{
/ / 글자 최대 기록 R [1] (즉, 쌓 기) 과 무질서 구역 의 마지막 기록 R [n] 을 교환 합 니 다.
a[0]=a[0]^a[i];
a[i]=a[0]^a[i];
a[0]=a[0]^a[i];
/ / a [0. i] 를 돔 으로 재 조정
HeapAdjust(a,0,i);
}
return;
}
int main(int argc, char const *argv[])
{
int a[]={45,569,213,123,12,56,45,56,10};
HeapSort(a,9);
int i;
for(i=0;i<9;i++)
{
printf("%d ",a[i]);
}
printf("");
return 0;
}

컴 파일 실행 결과 가 정확 합 니 다. 오류 가 있 으 면 지적 해 주 십시오.