PHP 정렬 알고리즘 시리즈의 버킷 정렬에 대한 자세한 설명

이 글에서는 주로 PHP 정렬 알고리즘 시리즈의 버킷 정렬을 모든 사람에게 자세히 소개합니다. 관심 있는 친구는

버킷 정렬(Bucket sort) 또는 소위 Bin 정렬을 참조할 수 있습니다. 배열을 제한된 수의 버킷으로 나누어 작동하는 정렬 알고리즘입니다. 각 버킷은 개별적으로 정렬됩니다(다른 정렬 알고리즘을 사용하거나 버킷 정렬을 계속 반복적으로 사용할 수 있음). 버킷 정렬은 비둘기집 정렬의 귀납적 결과입니다. 버킷 정렬은 정렬할 배열의 값이 고르게 분포되어 있을 때 선형 시간(Θ(n))을 사용합니다. 그러나 버킷 정렬은 비교 정렬이 아니며 하한 O(n log n)의 영향을 받지 않습니다.

Principle

양적 배열을 빈 버킷으로 설정합니다. 순서를 검색하여 항목을 해당 버킷에 하나씩 넣으세요.

비어 있지 않은 각 버킷을 정렬합니다.

비워지지 않은 버킷의 항목을 원래 순서로 다시 배치하세요.



예

정렬할 숫자를 가정해보자 [6 2 4 1 5 9]

빈 버킷 10개 준비, 빈 버킷의 최대 개수
[0 0 0 0 0 0 0 0 0 0] 비어 있음 buckets

[0 1 2 3 4 5 6 7 8 9] 버킷 번호 (실제로는 존재하지 않음)

1. 순차적으로 정렬할 숫자를 배열에서 먼저 빼낸 후 6을 꺼냅니다. 6번 버킷에 넣습니다. 프로세스는 다음과 유사합니다. 빈 버킷 [정렬할 배열[ 0] ] = 정렬할 배열[ 0]

[6 2 4 1 5 9] 정렬할 배열
[ 0 0 0 0 0 6 0 0 0] 빈 버킷

[0 1 2 3 4 5 6 7 8 9] 버킷 번호 (실제로는 존재하지 않음)

2 정렬할 배열에서 다음 번호를 꺼냅니다. . 이때 2를 꺼내서 2번 버킷에 담는다. 숫자는 몇 개나 넣을까?

[6 2 4 1 5 9] 정렬할 배열
[0 0 2 0 0 0 6 0 0 0] 빈 버킷

[0 1 2 3 4 5 6 7 8 9] 버킷 번호 (실제 존재하지 않음)

3,4,5,6 생략, 이후 과정은 동일 모두 버킷에 넣으면 이렇게 됩니다

[6 2 4 1 5 9] 정렬할 배열
[0 1 2 0 4 5 6 0 0 9] 빈 버킷

[0 1 2 3 4 5 6 7 8 9] 버킷 번호 (실제로 존재하지 않음)

0은 빈 버킷을 의미하므로 건너뛰고 순서대로 꺼내세요. 1 2 4 5 6 9


PHP 코드 구현

<?php
function bucket_sort($arr){
 $result=[];
 $length=count($arr);
 //入桶
 for($i=0,$max=$arr[$i];$i<$length;$i++){
  if ($max<$arr[$i]) {
   $max=$arr[$i];
  }
  $bucket[$arr[$i]]=[];
  array_push($bucket[$arr[$i]],$arr[$i]);
 }
 //出桶
 for($i=0;$i<=$max;$i++){
  if(!empty($bucket[$i])){
   $l=count($bucket[$i]);
   for ($j=0; $j <$l ; $j++) {
    $result[]=$bucket[$i][$j];
   }
  }
 }
 return $result;
}

위 이 기사의 전체 내용은 모든 사람의 학습에 도움이 되기를 바라며, 또한 모든 사람이 PHP 중국어 웹사이트를 지지하기를 바랍니다.

당신이 관심을 가질 만한 기사:

PHP 정렬 알고리즘 시리즈의 병합 정렬에 대한 자세한 설명_php 기술

PHP 정렬 알고리즘 시리즈의 직접 선택 정렬에 대한 자세한 설명

PHP 정렬 알고리즘 시리즈 삽입 정렬에 대한 자세한 설명

위 내용은 PHP 정렬 알고리즘 시리즈의 버킷 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!