집 > 기사 > 백엔드 개발 > PHP 힙 정렬 알고리즘 예제 분석

PHP 힙 정렬 알고리즘 예제 분석

php中世界最好的语言원래의: 2018-05-16 15:14:401607검색

이번에는 PHP 힙 정렬 알고리즘의 예제 분석을 가져오겠습니다. PHP 힙 정렬 알고리즘의 예제 분석에 대한 주의 사항은 무엇입니까? 다음은 실제 사례입니다.

앞서 언급했듯이 선택 정렬입니다. 정렬할 n개의 레코드 중에서 가장 작은 레코드를 선택하려면 n - 1번 비교해야 합니다. 이는 첫 번째 데이터를 찾는 데 매우 많은 비교가 필요하다는 것을 의미합니다. 그렇지 않으면 그가 가장 작은 기록이라는 것을 어떻게 알 수 있습니까?

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

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

기본 아이디어:

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

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

이것을 보고 "힙이 완전한 이진 트리인지"에 대한 의문도 생겼습니다. 인터넷에서 힙이 완전한 이진 트리인지 여부와 관계없이 완전한 이진 트리가 아니라고 말하는 사람들도 있습니다. 나무, 나는 여전히 내 의견을 유보합니다. 여기서는 주로 저장과 계산을 용이하게 하기 위해 완전한 이진 트리 형태의 큰 루트 힙(작은 루트 힙)을 사용한다는 점만 알아야 합니다(편의성은 나중에 살펴보겠습니다).

힙 정렬 알고리즘:

힙 정렬은 힙을 사용하여 정렬하는 방법입니다(큰 루트 힙을 가정). 기본 아이디어는 다음과 같습니다. 정렬할 시퀀스를 큰 루트 힙으로 구성합니다. 이때 전체 시퀀스의 최대값은 힙 상단의 루트 노드이다. 이를 제거하고(실제로 이를 힙 배열의 마지막 요소와 교환합니다. 이때 마지막 요소는 최대값입니다.) 그런 다음 나머지 n - 1개 시퀀스를 힙으로 재구성하여 n 요소를 얻습니다. 다음으로 가장 작은 값입니다. 이것을 반복해서 실행하면 순서가 있는 시퀀스를 얻을 수 있습니다.

큰 루트 힙 정렬 알고리즘의 기본 작업:

1힙 만들기 힙 만들기는 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는 노드와 상호 작용한 다음 힙 조정 프로세스를 호출합니다. 이것은 recursive 프로세스입니다. 힙을 조정하는 프로세스의 시간 복잡도는 힙의 깊이와 관련이 있습니다. 깊이 방향을 따라 조정되기 때문에 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);

실행 결과:

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) 的时间复杂度了。

堆排序是一种不稳定排序方法。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

PHP 힙 정렬 알고리즘 예제 분석

관련 기사