PHP 정렬 알고리즘 더미 정렬(Heap Sort)실례 상세 설명

이 실례 는 PHP 정렬 알고리즘 의 더미 정렬(Heap Sort)을 설명 한다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
알고리즘 도입:
여기 서 나 는 에서 의 시작 을 직접 인용 했다.
앞에서 말 했 듯 이대화 데이터 구조정렬 을 기다 리 는 n 개의 기록 에서 가장 작은 기록 을 선택 하려 면 n-1 번 을 비교 해 야 합 니 다.원래 이것 도 이해 할 수 있 습 니 다.첫 번 째 데 이 터 를 찾 으 려 면 이렇게 여러 번 비교 해 야 합 니 다.그렇지 않 으 면 그 가 가장 작은 기록 이라는 것 을 어떻게 알 수 있 습 니까?
안 타 깝 게 도 이런 조작 은 매번 의 비교 결 과 를 저장 하지 않 았 다.뒤의 것 이 비교적 무 겁 고 많은 비교 가 전에 이미 했 지만 지난번 에 정렬 할 때 이런 비교 결 과 를 저장 하지 않 았 기 때문에 다음 에 정렬 할 때 이런 비교 조작 을 반복 해서 실 행 했 기 때문에 기록 한 비교 횟수 가 비교적 많다.
매번 최소 기록 을 선택 하 는 동시에 비교 결과 에 따라 다른 기록 에 대해 해당 하 는 조정 을 할 수 있다 면 정렬 의 전체적인 효율 이 매우 높 을 것 이다.한편,쌓 기 정렬 은 간단 한 선택 정렬 을 개선 하 는 것 으로 이런 개선 효 과 는 매우 뚜렷 하 다.
기본 사상:
쌓 기 정렬 을 소개 하기 전에 쌓 기 를 소개 합 니 다.
에서 정의 한 바 와 같이 무 더 기 는 다음 과 같은 성질 을 가 진 완전 이 진 트 리 이다.모든 노드 의 값 은 그 좌우 아이의 노드 의 값 보다 크 거나 같 아서 큰 무더기(큰 무더기)가 된다.또는 모든 노드 의 값 이 좌우 노드 의 값 보다 작 거나 같 아서 작은 지붕 더미(작은 뿌리 더미)가 됩 니 다.
당시 에 나 는 이곳 을 보 았 을 때 도'더미 가 완전 이 진 트 리 인지 아 닌 지'에 대해 의문 을 가 진 적 이 있다.인터넷 에서 도 완전 이 진 트 리 가 아니 라 고 말 했 지만 완전히 이 진 트 리 가 되 든 안 되 든 의견 을 보류 했다.우 리 는 여기 서 우 리 는 완전히 이 진 트 리 형식의 큰 뿌리 더미(작은 굽 더미)를 사용 하 는데 주로 저장 과 계산 을 편리 하 게 하기 위해 서 이다.

쌓 기 정렬 알고리즘:
쌓 기 정렬 은 쌓 기(큰 뿌리 더 미 를 이용 한 가설)를 이용 하여 정렬 하 는 방법 이다.그의 기본 사상 은 정렬 할 서열 을 큰 뿌리 로 구성 하 는 것 이다.이때 전체 서열 의 최대 치 는 지붕 의 뿌리 노드 이다.이 를 옮 기 고(사실은 배열 의 끝 요소 와 교환 하 는 것 입 니 다.이때 끝 요 소 는 최대 치 입 니 다)남 은 n-1 개의 서열 을 하나의 더미 로 재 구성 하면 n 개의 요소 중 작은 값 을 얻 을 수 있 습 니 다.이렇게 반복 적 으로 집행 하면 질서 있 는 서열 을 얻 을 수 있다.
큰 루트 정렬 알고리즘 의 기본 동작:
① 쌓 기,쌓 기 는 쌓 기 를 계속 조정 하 는 과정 으로 len/2 에서 부터 조정 하고 첫 번 째 노드 까지 여기 len 은 쌓 인 요소 의 개수 이다.쌓 아 올 리 는 과정 은 선형 과정 으로 len/2 에서 0 까지 쌓 아 올 리 는 과정 을 계속 호출 하여 o(h1)+o(h2)...+o(hlen/2)에서 h 는 노드 의 깊이 를 나타 내 고 len/2 는 노드 의 개 수 를 나타 내 는데 이것 은 화 해 를 구 하 는 과정 이 고 결 과 는 선형 O(n)이다.
② 쌓 기 조정:쌓 기 를 구축 하 는 과정 에서 사용 되 고 쌓 기 정렬 과정 에서 도 사용 된다.이용 하 는 사상 은 노드 i 와 그의 아이 노드 left(i),right(i)를 비교 하고 세 사람의 최대(또는 최소)자 를 선택 하 는 것 이다.만약 에 최대(작은)값 이 노드 i 가 아니 라 그의 아이 노드 이 고 저쪽 의 상호작용 노드 i 와 이 노드 를 선택 한 다음 에 더 미 를 조정 하 는 과정 을 호출 하 는 것 이 순환 하 는 과정 이다.쌓 아 올 리 는 과정 시간 복잡 도 는 쌓 아 올 리 는 깊이 와 관계 가 있 고 lgn 의 조작 입 니 다.깊이 방향 을 따라 조정 하기 때 문 입 니 다.
③ 쌓 기 정렬:쌓 기 정렬 은 위의 두 가지 과정 을 이용 하여 이 루어 진다.우선 요소 에 따라 더 미 를 구축 하 는 것 이다.그 다음 에 쌓 인 뿌리 노드 를 꺼 내 고(보통 마지막 노드 와 교환)앞의 len-1 개 노드 를 계속 쌓 아서 조정 하 는 과정 을 한 다음 에 뿌리 노드 를 꺼 내 서 모든 노드 가 꺼 낼 때 까지 합 니 다.정렬 과정의 시간 복잡 도 는 O(nlgn)입 니 다.쌓 는 시간의 복잡 도 는 O(n)이기 때문이다.쌓 아 올 리 는 시간 복잡 도 는 lgn 이 고 n-1 회 호출 되 었 기 때문에 쌓 아 올 리 는 시간 복잡 도 는 O(nlgn)입 니 다.
이 과정 에서 많은 그림 이 있어 야 알 수 있 지만 나 는 게으르다.
알고리즘 구현:

<?php
//   （          ）
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//   $arr[$start]    ， $arr[$start]、$arr[$start+1]、、、$arr[$end]       （           ）
//       s        2*s + 1   2*s+2 （        0  ）
function HeapAdjust(array &$arr,$start,$end){
  $temp = $arr[$start];
  //               
  //      （           0）
  //   2 * $start + 1，   2 * $start + 2
  for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
    if($j != $end && $arr[$j] < $arr[$j + 1]){
      $j ++; //      
    }
    if($temp >= $arr[$j]){
      break; //       
    }
    //              
    $arr[$start] = $arr[$j];
    //    
    $start = $j;
  }
  $arr[$start] = $temp;
}
function HeapSort(array &$arr){
  $count = count($arr);
  //          （        ，     floor($count/2)-1，                    )
  for($i = floor($count / 2) - 1;$i >= 0;$i --){
    HeapAdjust($arr,$i,$count);
  }
  for($i = $count - 1;$i >= 0;$i --){
    //              ，       （          ），           
    swap($arr,0,$i);
    //    ，       （    ）     ，         ($arr[0...$i-1])        
    HeapAdjust($arr,0,$i - 1);
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

실행 결과:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

시간 복잡 도 분석:
그것 의 운행 시간 은 초기 구축 과 재건 축 똥 의 반복 적 인 선별 에 소모 된다.
전체적으로 볼 때 쌓 아 올 리 는 시간의 복잡 도 는 O(nlogn)이다.쌓 기 정렬 은 원본 기록 의 정렬 상태 에 민감 하지 않 기 때문에 가장 좋 고 최 악의 시간 복잡 도 는 모두 O(nlogn)이다.이것 은 성능 에 있어 서 거품 이 생기 고 간단 한 선택,직접 삽입 하 는 O(n^2)보다 훨씬 좋 은 시간 복잡 도 를 가 져 야 한다.
쌓 기 정렬 은 불안정 정렬 방법 이다.
본 고 는 을 참고 하여 여기 서 기록 만 하고 나중에 조회 하기에 편리 하 며 큰 신 은 뿌리 지 마 세 요!
PS:정렬 에 관 한 프 리 젠 테 이 션 도 구 를 추천 합 니 다.참고 하 시기 바 랍 니 다.
온라인 애니메이션 프레젠테이션 삽입/선택/거품/병합/힐/빠 른 정렬 알고리즘 프로 세 스 도구:
단순 선택 정렬
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.