PHP 정렬 알고리즘 시리즈 버킷 정렬 상세 설명

PHP 정렬 알고리즘 시리즈 버킷 정렬 상세 설명_php 기술

小云云

풀어 주다： 2023-03-19 11:06:02

원래의

1722명이 탐색했습니다.

이 기사는 주로 PHP 정렬 알고리즘 시리즈의 버킷 정렬을 모든 사람에게 자세히 소개합니다. 관심 있는 친구가 참조할 수 있기를 바랍니다.

버킷 정렬

버킷 정렬, 또는 소위 빈 정렬은 배열을 제한된 수의 버킷으로 나누어 작동하는 정렬 알고리즘입니다. 각 버킷은 개별적으로 정렬됩니다(다른 정렬 알고리즘을 사용하거나 버킷 정렬을 계속 반복적으로 사용할 수 있음). 버킷 정렬은 비둘기집 정렬의 귀납적 결과입니다. 버킷 정렬은 정렬할 배열의 값이 고르게 분포되어 있을 때 선형 시간(Θ(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 코드 Realize

<?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;
}

로그인 후 복사