PHP 기반 정렬 원리 및 인 스 턴 스 상세 설명

쌓다
더미(hep)는 컴퓨터 과학 에서 특수 한 데이터 구 조 를 통칭 하 는 것 으로 보통 나무 로 볼 수 있 는 배열 대상 이다.
{k1,k2,ki,...,kn}(ki<=k2i,ki<=k2i+1)|(ki>=k2i,ki>=k2i+1),(i=1,2,3,4...n/2)
더미 에 대하 여:
4.567917.더미 중의 특정한 노드 의 값 은 항상 아버지 노드 의 값 보다 크 거나 작 지 않다4.567917.무 더 기 는 항상 완전 이 진 트 리(아래)이다4.567917.뿌리 노드 의 가장 큰 더 미 를 최대 더미 또는 큰 뿌리 더미 라 고 부 르 고 뿌리 노드 의 가장 작은 더 미 를 최소 더미 또는 작은 뿌리 더미 라 고 부른다완전 이 진 트 리
쌓 기 서열 이 라 고 하면 완전 이 진 트 리 를 언급 하지 않 을 수 없다.이런 기본 개념 들 은 인터넷 곳곳에 있 는데 나 는 가장 간단 한 것 을 땄 다.
완전 이 진 트 리:마지막 층 을 제외 하고 모든 층 의 노드 수 는 최대 치 에 달 합 니 다.마지막 층 에는 오른쪽 에 있 는 몇 개의 결점 만 부족 하 다.
내 가 정리 한 것 은 바로 다음 과 같은 두 가지 특징 이 있 기 때 문 이 라 고 생각한다.
4.567917.마지막 층 에 빈자리 가 있 고 오른쪽 에 빈자리 가 있 는 것 만 허용 한다.즉,잎 결점 은 층 이 가장 큰 2 층 에서 만 나타 날 수 있다(저장 방식 의 규칙 성)

만약 i>1,tree 의 부 모 는 tree[i div 2](부자 결점 값 의 규칙 성)이다

정렬 이 편리 합 니 다.
더미 정렬
쌓 아 올 리 는 순 서 는 큰 지붕 으로 쌓 고 내 리 는 순 서 는 작은 지붕 으로 쌓 아야 한다.
이 예 는 내림차 순 서 를 구 하 는 작은 지붕 더미 로 해석 된다.
쌓 기 정렬 단 계 는 다음 과 같 습 니 다:
1.우 리 는 데이터(49,38,65,97,76,13,27,50)를 배열$arr 로 만 듭 니 다.
2.배열$arr 로 작은 지붕 더 미 를 만 듭 니 다(주요 절 차 는 코드 주석 에서 설명 합 니 다.아래 그림 은 하나의 배열 로 작은 지붕 더 미 를 만 드 는 과정 입 니 다).
3.쌓 인 뿌리(가장 작은 원소)를 마지막 잎 과 교환 하고 쌓 인 길 이 를 하나 줄 이 고 두 번 째 단계 로 뛰 기;
4.2-3 단 계 를 반복 하여 쌓 여 있 는 노드 가 하나 밖 에 없 을 때 까지 정렬 이 완 료 됩 니 다.

정렬 된 PHP 구현

//     ,   0  ,  ,   n         2n+1,     2n+2; 
//    ,     
$arr=array(49,38,65,97,76,13,27,50);
$arrSize=count($arr);

//         ，                。
buildHeap($arr,$arrSize);

for($i=$arrSize-1;$i>0;$i--){
  swap($arr,$i,0);
  $arrSize--;
  buildHeap($arr,$arrSize);  
}

//        
function buildHeap(&$arr,$arrSize){
  //         $index,  ,   "97"    ,               ,          
  // $index           ,     
  for($index=intval($arrSize/2)-1; $index>=0; $index--){
    //      ,         $min
    if($index*2+1<$arrSize){
      $min=$index*2+1;
      //       ,         ,        ,             $min
      if($index*2+2<$arrSize){
        if($arr[$index*2+2]<$arr[$min]){
          $min=$index*2+2;
        }
      }
      //              ,      ,        ,      
      if($arr[$min]<$arr[$index]){
        swap($arr,$min,$index);
      }  
    }
  }
}

//          $arr    $one $another   
function swap(&$arr,$one,$another){
  $tmp=$arr[$one];
  $arr[$one]=$arr[$another];
  $arr[$another]=$tmp;
}

다음은 정렬 의 최종 결과 입 니 다.

쌓 기 는 전체 정렬 에 사용 되 며,시간 복잡 도 는 O(nlogn)입 니 다.
빠 른 배열 은 전체 정렬 에 사용 되 고 평균 시간 복잡 도 역시 O(nlogn)이다.
그러나 쌓 기 정렬 은 TopK 를 구 할 때 쌓 는 시간의 복잡 도 는 O(Klog 2(n)로 K 라운드 정렬 만 하면 되 기 때문이다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.