집 > 기사 > 백엔드 개발 > PHP 계산 정렬 알고리즘 구현(코드 예)

PHP 계산 정렬 알고리즘 구현(코드 예)

藏色散人원래의: 2019-03-11 10:30:303160검색

카운팅 정렬은 작은 정수 키를 기반으로 개체 집합을 정렬하는 알고리즘입니다. 즉, 정수 정렬 알고리즘입니다. 서로 다른 키 값을 가진 개체 수를 계산하고 이러한 숫자에 대한 산술을 사용하여 출력 시퀀스에서 각 키 값의 위치를 결정합니다.

카운팅 정렬은 키 변경이 총 요소 수보다 크지 않은 경우에만 사용하기에 적합합니다. 더 큰 키를 효율적으로 처리할 수 있는 다른 정렬 알고리즘(기수 정렬)의 서브루틴으로 자주 사용됩니다.

간단히 말하면 계수 정렬은 안정적인 선형 시간 정렬 알고리즘입니다. 계산 정렬은 추가 배열 C를 사용합니다. 여기서 i번째 요소는 정렬할 배열 A에서 값이 i와 동일한 요소 수입니다. 그런 다음 배열 C에 따라 A의 요소를 올바른 위치에 배열합니다.

계산 정렬 알고리즘의 일반적인 구현 단계는 다음과 같습니다.

1. 정렬할 배열에서 가장 큰 요소와 가장 작은 요소를 찾습니다.

2. 배열에서 값이 i인 각 요소의 발생 횟수를 계산합니다. , 저장 배열 C의 i번째 항목을 입력합니다.

3. 모든 개수를 누적합니다(C의 첫 번째 요소부터 시작하여 각 항목이 이전 항목에 추가됨).

4. 각 요소 i는 새 배열의 C[i]번째 항목에 배치되고 배치된 각 요소에 대해 C[i]에서 1을 뺍니다.

PHP 계산 정렬 알고리즘의 구현 코드 예는 다음과 같습니다.

<?php
function counting_sort($my_array, $min, $max)
{
    $count = array();
    for($i = $min; $i <= $max; $i++)
    {
        $count[$i] = 0;
    }

    foreach($my_array as $number)
    {
        $count[$number]++;
    }
    $z = 0;
    for($i = $min; $i <= $max; $i++) {
        while( $count[$i]-- > 0 ) {
            $my_array[$z++] = $i;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,counting_sort($test_array, -1, 5)). PHP_EOL;

출력:

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 :-1, 0, 1, 2, 3, 4, 5

PHP 계산 정렬 알고리즘 구현(코드 예)

관련 기사