PHP를 사용하여 역순 알고리즘을 구현하는 방법

PHP에서 역순 알고리즘을 구현하는 방법

컴퓨터 과학에서는 ai와 aj의 두 요소에 대해 i < j 및 ai > . 역순 문제를 해결하는 것은 실질적인 의미가 크며 정렬 문제 최적화 및 데이터 분석과 같은 분야에 적용됩니다.

이 기사에서는 이 일반적인 문제를 더 잘 이해하고 마스터하기 위해 PHP 프로그래밍 언어를 사용하여 역방향 쌍 알고리즘을 구현하는 방법을 소개합니다.

먼저 역순쌍을 계산하는 방법에 대해 생각해야 합니다. 간단한 접근 방식은 두 개의 중첩 루프를 사용하여 매번 모든 요소 쌍을 비교하는 것입니다. ai > aj 조건이 ​​충족되면 역방향 쌍의 카운터를 증가시킵니다. 그러나 이 방법의 시간 복잡도는 O(n^2)이므로 대규모 데이터 세트에는 적합하지 않습니다.

또 다른 효율적인 방법은 병합 정렬 알고리즘을 사용하는 것입니다. 이 알고리즘의 기본 아이디어는 시퀀스를 더 작은 하위 시퀀스로 분해한 다음 이를 더 큰 정렬된 시퀀스로 병합하는 것입니다. 병합 과정에서 쌍의 수를 역순으로 쉽게 계산할 수 있습니다.

다음은 PHP 프로그래밍 언어를 사용하여 역순 쌍 알고리즘을 구현하기 위한 샘플 코드입니다.

function mergeSortCount(&$arr) {
    $temp = array();
    $count = 0;
    $length = count($arr);
    $temp = array_fill(0, $length, 0); // 创建一个临时数组用于存储合并过程中的结果

    $count = mergeSort($arr, $temp, 0, $length - 1); // 调用真正的归并排序函数

    return $count;
}

function mergeSort(&$arr, &$temp, $left, $right) {
    $count = 0;
    if ($left < $right) {
        $mid = floor(($left + $right) / 2); // 找到中间位置
        $count += mergeSort($arr, $temp, $left, $mid); // 递归地对左子数组进行排序
        $count += mergeSort($arr, $temp, $mid + 1, $right); // 递归地对右子数组进行排序
        $count += merge($arr, $temp, $left, $mid + 1, $right); // 合并左右子数组，并计算逆序对数量
    }
    return $count;
}

function merge(&$arr, &$temp, $left, $mid, $right) {
    $count = 0;
    $i = $left; // 左子数组起始位置
    $j = $mid; // 右子数组起始位置
    $k = $left; // 合并后的数组起始位置

    while ($i <= $mid - 1 && $j <= $right) {
        if ($arr[$i] <= $arr[$j]) {
            $temp[$k++] = $arr[$i++];
        } else {
            $temp[$k++] = $arr[$j++];
            $count += $mid - $i;
        }
    }

    while ($i <= $mid - 1) {
        $temp[$k++] = $arr[$i++];
    }

    while ($j <= $right) {
        $temp[$k++] = $arr[$j++];
    }

    for ($i = $left; $i <= $right; $i++) {
        $arr[$i] = $temp[$i];
    }

    return $count;
}

// 测试示例
$arr = array(3, 1, 2, 4, 5);
$count = mergeSortCount($arr);
echo "逆序对的数量：" . $count;

위 코드는 먼저 배열을 매개 변수로 받아들이고 반환하는 mergeSortCount 함수를 정의합니다. 역순 쌍의 수. 이 함수에서는 임시 배열 temp를 만들고, 카운터 count를 초기화하고, 배열 length의 길이를 기록합니다. mergeSortCount函数，该函数接受一个数组作为参数，并返回逆序对的数量。在这个函数中，我们创建了一个临时数组temp，并初始化一个计数器count，以及记录数组长度length。

接下来，我们调用mergeSort函数进行实际的归并排序。mergeSort函数接受一个左闭区间$left和一个右闭区间$right作为参数，在每次递归调用中，它将分割数组并递归地对子数组进行排序，然后调用merge函数来合并子数组并计算逆序对的数量。

在merge函数中，我们使用三个指针$i、$j和$k，对左、右子数组和合并后的数组进行遍历。如果左子数组的当前元素小于或等于右子数组的当前元素，则将左子数组的当前元素放入临时数组中，并将$i和$k指针向后移动一位。如果右子数组的当前元素小于左子数组的当前元素，则将右子数组的当前元素放入临时数组中，并将$j和$k指针向后移动一位。在这个过程中，如果出现右子数组的当前元素小于左子数组的当前元素，则计数器$count加上左子数组当前位置到中间位置的元素个数（因为左子数组已经有序）。

最后，我们将临时数组$temp中的元素复制回原始数组$arr，然后返回计数器$count。

在最后的测试示例中，我们定义了一个包含5个整数的数组，并调用mergeSortCount

다음으로 mergeSort 함수를 호출하여 실제 병합 정렬을 수행합니다. mergeSort 함수는 왼쪽 닫힌 간격 $left와 오른쪽 닫힌 간격 $right를 매개변수로 허용합니다. 각 재귀 호출에서 배열을 분할합니다. 하위 배열을 재귀적으로 정렬한 다음 merge 함수를 호출하여 하위 배열을 병합하고 역방향 쌍의 수를 계산합니다.

merge 함수에서는 세 개의 포인터 $i, $j 및 $k를 사용합니다. 왼쪽 및 오른쪽 하위 배열과 병합된 배열이 순회됩니다. 왼쪽 하위 배열의 현재 요소가 오른쪽 하위 배열의 현재 요소보다 작거나 같은 경우 왼쪽 하위 배열의 현재 요소를 임시 배열에 넣고 $i 및 $를 추가합니다. k code>포인터가 한 위치 뒤로 이동합니다. 오른쪽 하위 배열의 현재 요소가 왼쪽 하위 배열의 현재 요소보다 작은 경우 오른쪽 하위 배열의 현재 요소를 임시 배열에 넣고 <code>$j 및 $k를 추가합니다. code> 포인터가 한 위치 뒤로 이동합니다. 이 과정에서 오른쪽 하위 배열의 현재 요소가 왼쪽 하위 배열의 현재 요소보다 작은 경우 왼쪽 하위 배열의 현재 위치부터 다음 요소까지의 요소 수에 <code>$count 카운터가 추가됩니다. 중간 위치입니다(왼쪽 하위 배열이 이미 정렬되어 있기 때문입니다). 🎜🎜마지막으로 임시 배열 $temp의 요소를 원래 배열 $arr로 다시 복사한 다음 카운터 $count를 반환합니다. . 🎜🎜마지막 테스트 예에서는 5개의 정수가 포함된 배열을 정의하고 mergeSortCount 함수를 호출하여 역순 쌍의 수를 계산했습니다. 이 예에서 역방향 쌍의 수는 2입니다. 🎜🎜위의 코드 예제를 통해 PHP 프로그래밍 언어를 사용하여 역방향 쌍 알고리즘을 구현하는 것이 어렵지 않다는 것을 알 수 있습니다. 병합 정렬 알고리즘의 핵심 아이디어는 시퀀스를 더 작은 하위 시퀀스로 분해하고 병합 작업을 통해 정렬을 구현하며 동시에 역순 쌍의 수를 계산하는 것입니다. 이는 다양한 실제 문제에 적용할 수 있는 효율적이고 일반적으로 사용되는 정렬 알고리즘입니다. 🎜

위 내용은 PHP를 사용하여 역순 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!