PHP에서 기수 정렬 알고리즘의 구현 단계 및 시간 복잡도 분석.

PHP에서 기수 정렬 알고리즘의 구현 단계 및 시간 복잡도 분석

Radix 정렬은 일반적으로 사용되는 선형 시간 복잡도(O(n)) 정렬 알고리즘으로, 정렬을 달성하기 위해 비트별 비교 및 ​​할당 요소를 사용합니다. . 이 기사에서는 기수 정렬 알고리즘의 구현 단계를 소개하고 시간 복잡도를 분석합니다.

기수 정렬의 기본 아이디어는 비교할 모든 요소(양의 정수)를 제한된 수의 버킷에 할당한 다음 각 버킷의 요소를 차례로 수집하여 최종적으로 정렬을 완료하는 것입니다.

구현 단계는 다음과 같습니다.

1. 버킷 배열 초기화: 버킷을 나타내는 2차원 배열을 생성합니다. 각 버킷은 1차원 배열입니다. 버킷 수는 정렬할 요소의 최대 자릿수에 따라 결정됩니다.
2. 최대 자릿수 찾기: 정렬할 배열을 탐색하고 가장 큰 요소를 찾아 해당 자릿수를 결정합니다.
3. 비트 단위로 배포 및 수집: 낮은 비트에서 높은 비트로 각 요소의 해당 비트 수 값을 차례로 꺼내 해당 요소를 해당 버킷에 할당합니다. 그런 다음 버킷 순서대로 원래 배열로 다시 수집합니다.
4. 3단계 반복: 가장 높은 비트가 할당될 때까지 높은 비트를 순서대로 할당하고 수집합니다.
5. 완전 정렬: 여러 번 할당하고 수집한 후 정렬할 배열이 정렬되었습니다.

다음은 기수 정렬의 PHP 코드 예입니다.

function radixSort(array $arr): array {
    // 找到待排序数组的最大值
    $max = max($arr);
    
    // 确定最大值的位数
    $maxDigit = strlen((string)$max);
    
    // 初始化桶数组
    $buckets = [];
    for ($i = 0; $i < 10; $i++) {
        $buckets[$i] = [];
    }
    
    // 依次按位进行分配和收集
    for ($digit = 1; $digit <= $maxDigit; $digit++) {
        // 分配到桶中
        foreach ($arr as $num) {
            $index = ($num / pow(10, $digit - 1)) % 10;
            array_push($buckets[$index], $num);
        }
        
        // 按照桶的顺序进行收集
        $pos = 0;
        for ($i = 0; $i < 10; $i++) {
            while (!empty($buckets[$i])) {
                $arr[$pos] = array_shift($buckets[$i]);
                $pos++;
            }
        }
    }
    
    return $arr;
}

// 测试
$arr = [170, 45, 75, 90, 802, 24, 2, 66];
$result = radixSort($arr);
print_r($result);

시간 복잡도 분석:

• 정렬할 요소의 자릿수가 d이고 버킷의 수가 k라면 시간 복잡도는 기수 정렬은 O(d * (n + k))입니다.
• 최악의 경우 정렬해야 할 요소의 비트 수는 버킷 수, 즉 d = k이고 시간 복잡도는 O(2 * n)입니다.
• 일반적인 상황에서 정렬할 요소의 자릿수는 버킷 수와 관련이 없습니다. 즉, 이때 시간 복잡도는 O(n)입니다.

기수 정렬은 선형 시간 복잡도를 달성할 수 있지만 공간 복잡도가 높고 요소를 저장하려면 추가 버킷 배열이 필요합니다. 또한, 음수를 처리하는 경우 요소에 대한 변환 및 반전 연산도 필요합니다. 그러나 실제 응용 프로그램에서 정렬할 데이터가 작거나 환경에 충분한 메모리가 있는 경우 기수 정렬은 여전히 ​​효율적인 정렬 알고리즘입니다.

요약하자면, 이 글은 PHP에서 기수 정렬 알고리즘의 구현 단계를 소개하고 시간 복잡도를 분석합니다. 기수 정렬은 요소를 비트 단위로 비교하고 할당함으로써 정렬 작업을 효율적으로 완료할 수 있습니다. 실제 애플리케이션을 작성할 때 정렬할 요소의 특성에 따라 적절한 정렬 알고리즘을 선택하면 성능을 향상시킬 수 있습니다.

위 내용은 PHP에서 기수 정렬 알고리즘의 구현 단계 및 시간 복잡도 분석.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!