집 > 기사 > 백엔드 개발 > PHP 정렬 알고리즘 힙 정렬에 대한 자세한 설명

PHP 정렬 알고리즘 힙 정렬에 대한 자세한 설명

小云云원래의: 2018-01-08 10:08:271646검색

이 글은 주로 PHP에서 구현된 Heap Sort 알고리즘을 자세히 소개합니다. 관심 있는 친구들이 참고하면 도움이 될 것입니다.

알고리즘 소개:

여기서 "Dahua 데이터 구조"의 시작 부분을 직접 인용합니다.

앞서 언급했듯이 정렬할 n개의 레코드 중에서 가장 작은 레코드를 선택하는 단순 선택 정렬은 n - 1의 비교가 필요합니다. 이것은 이해할 수 있는 일입니다. 첫 번째 데이터를 찾기 위해 여러 번 비교하는 것이 정상입니다. 그렇지 않으면 그것이 가장 작은 레코드인지 알 수 있습니다.

안타깝게도 이 작업은 각 패스의 비교 결과를 저장하지 않습니다. 이전 패스에서 많은 비교가 수행되었지만 정렬 중에 이전 패스가 저장되지 않았기 때문입니다. 이러한 비교 작업은 다음 정렬 단계에서 반복되므로 더 많은 비교가 기록됩니다.

매번 가장 작은 레코드를 선택하고 비교 결과에 따라 다른 레코드를 적절하게 조정할 수 있다면 전반적인 정렬 효율성이 매우 높아질 것입니다. 힙 정렬은 단순 선택 정렬을 개선한 것으로, 이러한 개선의 효과는 매우 분명합니다.

기본 아이디어:

힙 정렬을 소개하기 전에 먼저 힙에 대해 소개하겠습니다.

"Dahua 데이터 구조"의 정의: 힙은 다음 속성을 갖는 완전한 이진 트리입니다. 각 노드의 값이 더 큽니다. 보다 또는 왼쪽 및 오른쪽 자식 노드의 값과 같으면 큰 상단 힙(대형 루트 힙)이 됩니다. 또는 각 노드의 값이 왼쪽 및 오른쪽 노드의 값보다 작거나 같으면 , 작은 최상위 힙(작은 루트 힙)이 됩니다.

저도 이걸 보고 '힙이 완전한 이진 트리인가'라는 의문이 들었습니다. 나무, 나는 여전히 내 의견을 유보합니다. 여기서는 주로 저장과 계산을 용이하게 하기 위해 완전한 이진 트리 형태의 큰 루트 힙(작은 루트 힙)을 사용한다는 점만 알아야 합니다(편의성은 나중에 살펴보겠습니다).

힙 정렬 알고리즘:

힙 정렬은 힙을 사용하여 정렬하는 방법입니다(큰 루트 힙을 가정). 기본 아이디어는 정렬할 시퀀스를 큰 루트 힙으로 구성하는 것입니다. 이때 전체 시퀀스의 최대값은 힙 상단의 루트 노드이다. 이를 제거하고(실제로 이를 힙 배열의 마지막 요소와 교환합니다. 이때 마지막 요소는 최대값입니다), 나머지 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)(1회 호출)이므로 힙을 조정하는 데 드는 시간 복잡도는 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);

시간 복잡도 분석:

실행 시간은 초기 건설 쌍과 재구성 파일의 반복 심사에서만 소비됩니다.

일반적으로 힙 정렬의 시간 복잡도는 O(nlogn)입니다. 힙 정렬은 원본 레코드의 정렬 상태에 민감하지 않으므로 최고, 최악, 평균 시간 복잡도는 O(nlogn)입니다. 이는 버블링, 단순 선택 및 직접 삽입의 O(n^2) 시간 복잡도보다 성능 면에서 훨씬 더 좋습니다.

PHP 정렬 알고리즘 힙 정렬에 대한 자세한 설명

관련 기사