PHP에서 정렬 알고리즘 계산의 구현 원리

PHP에서 카운팅 정렬 알고리즘 구현 원리

카운팅 정렬은 비비교 정렬 알고리즘의 기본 아이디어는 각 요소의 발생 횟수를 계산한 다음 요소의 크기에 따라 정렬된 위치에 배치하는 것입니다. 카운팅 정렬은 요소의 범위가 작고 반복되는 요소가 많은 상황에 적합하며 시간 복잡도는 O(n)이며 효율적인 정렬 알고리즘입니다.

구현 원리:

1. 먼저 정렬할 배열을 순회하고 최대값과 최소값을 찾아 카운트 배열의 크기를 결정합니다.
2. 최대값과 최소값의 차이에 1을 더한 길이의 카운트 배열을 생성하고 0으로 초기화합니다.
3. 다시 정렬할 배열을 순회하면서 각 요소의 발생 횟수를 세어 그 숫자를 count 배열에 저장합니다.
4. 카운트 배열에 대해 누적 연산을 수행합니다. 즉, 현재 위치의 요소와 이전 위치의 요소를 합산합니다.
5. 정렬할 배열과 동일한 길이의 임시 배열을 만들어 정렬 결과를 저장하세요.
6. 정렬할 배열을 뒤에서 앞으로 탐색하고, 카운트 배열에 누적된 값을 사용하여 임시 배열의 해당 위치에 요소를 배치합니다.
7. 임시 배열의 요소를 원래 배열에 복사하여 정렬을 완료하세요.

다음은 PHP 코드 예제입니다.

function countSort($arr) {
    $min = min($arr); // 寻找最小值
    $max = max($arr); // 寻找最大值
    $count = array_fill($min, $max - $min + 1, 0); // 创建计数数组

    foreach ($arr as $num) {
        $count[$num]++; // 统计每个元素的出现次数
    }

    for ($i = $min + 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1]; // 计算累加值
    }

    $temp = array_fill(0, count($arr), 0); // 创建临时数组

    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $temp[--$count[$arr[$i]]] = $arr[$i]; // 将元素放置到临时数组中的相应位置上
    }

    for ($i = 0; $i < count($arr); $i++) {
        $arr[$i] = $temp[$i]; // 将临时数组中的元素复制到原始数组中
    }

    return $arr;
}

// 测试示例
$arr = [8, 3, 5, 4, 7, 6, 1, 6, 4, 4];
$result = countSort($arr);
echo implode(' ', $result); // 输出：1 3 4 4 4 5 6 6 7 8

위는 PHP에서 계산 정렬 알고리즘의 구현 원리입니다. 각 요소의 발생 횟수를 세고 해당 요소를 순서에 따라 배치합니다. 번호, 정렬된 배열이 정렬을 구현합니다. 이 알고리즘은 요소의 범위가 작고 반복되는 요소가 많은 상황에 적합하며, 정렬 작업을 더 짧은 시간에 완료할 수 있습니다.

위 내용은 PHP에서 정렬 알고리즘 계산의 구현 원리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!