PHP에서 정렬되지 않은 배열에서 중앙값을 찾는 방법

PHP에서 배열은 매우 강력한 데이터 구조입니다. PHP 배열을 사용하면 대량의 데이터를 쉽게 저장하고 조작할 수 있습니다. 하지만 정렬되지 않은 배열에서 중앙값을 찾아야 할 때는 어떻게 해야 할까요?

중앙값(중앙값이라고도 함)은 배열의 중간 값으로, 배열을 두 부분으로 나누며, 왼쪽의 모든 값은 그보다 작고 오른쪽의 모든 값은 더 큽니다. 배열에 짝수 개의 요소가 있는 경우 중앙값은 가운데 두 요소의 평균입니다.

PHP는 배열을 정렬하는 데 사용할 수 있는 sort() 함수를 제공하지만 큰 배열을 정렬할 때 이 함수의 시간 복잡도는 O(nlogn)에 도달하여 배열의 정렬 순서를 수정하게 됩니다. 우리는 원한다.

그렇다면 PHP에서 배열 순서를 변경하지 않고 순서가 지정되지 않은 배열의 중앙값을 어떻게 찾을 수 있을까요? 아래를 살펴보겠습니다.

1. 빠른 정렬을 사용하여 중앙값 찾기

빠른 정렬 알고리즘은 비교 기반 정렬 알고리즘으로 평균 시간 복잡도가 O(nlogn)이며 추가 메모리 공간이 필요하지 않습니다. 따라서 빠른 정렬을 사용하여 배열을 정렬하고 중앙값을 찾을 수 있습니다.

빠른 정렬 알고리즘의 주요 아이디어는 배열에서 벤치마크 요소를 선택한 다음 배열을 두 부분으로 나누는 것입니다. 한 부분에는 벤치마크 요소보다 작은 모든 값이 포함되고 다른 부분에는 벤치마크 요소보다 큰 모든 값을 포함합니다. 이 두 부분은 전체 배열이 정렬될 때까지 재귀적으로 정렬됩니다.

정렬되지 않은 배열의 중앙값을 찾으려면 먼저 빠른 정렬 알고리즘을 사용하여 정렬한 다음 정렬된 배열의 길이를 기준으로 중앙값을 결정할 수 있습니다.

다음은 빠른 정렬을 사용하여 중앙값을 찾는 PHP 코드의 예입니다.

function quickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $pivot = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for($i=1; $i<$len; $i++){
        if($arr[$i] <= $pivot){
            $left_arr[] = $arr[$i];
        }else{
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);
    return array_merge($left_arr, array($pivot), $right_arr);
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
$sorted_arr = quickSort($arr);
$len = count($sorted_arr);
if($len % 2 == 0){
    $middle = ($sorted_arr[$len/2-1] + $sorted_arr[$len/2])/2;
}else{
    $middle = $sorted_arr[($len-1)/2];
}
echo "中数为：".$middle;

2. 힙 정렬을 사용하여 중앙값 찾기

힙 정렬 알고리즘은 힙 기반 트리 데이터 구조를 기반으로 하는 정렬 알고리즘입니다. . 힙 정렬에서는 최대 힙 또는 최소 힙을 만들어 배열을 정렬합니다. 정렬되지 않은 배열의 중앙값을 찾기 위해 최대 힙을 사용할 수 있습니다.

Max 힙은 다음 속성을 만족하는 이진 트리입니다.

1. 힙의 각 노드 값은 왼쪽 및 오른쪽 자식 노드의 값보다 크거나 같습니다.

2. 힙은 항상 완전한 이진 트리입니다.

순서가 지정되지 않은 배열의 경우 최대 힙을 만들어 정렬할 수 있습니다. 그런 다음 최대 힙의 속성을 기반으로 중앙값을 찾을 수 있습니다.

다음은 힙 정렬을 사용하여 중간 숫자를 찾는 PHP 코드의 예입니다.

function buildMaxHeap(&$arr, $index, $heapSize){
    $left = 2*$index+1;
    $right = 2*$index+2;
    $max = $index;
    if($left<$heapSize && $arr[$left]>$arr[$max]){
        $max = $left;
    }
    if($right<$heapSize && $arr[$right]>$arr[$max]){
        $max = $right;
    }
    if($max != $index){
        $temp = $arr[$index];
        $arr[$index] = $arr[$max];
        $arr[$max] = $temp;
        buildMaxHeap($arr, $max, $heapSize);
    }
}

function heapSort(&$arr){
    $heapSize = count($arr);
    for($i=intval($heapSize/2)-1; $i>=0; $i--){
        buildMaxHeap($arr, $i, $heapSize);
    }
    for($i=$heapSize-1; $i>=1; $i--){
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        $heapSize--;
        buildMaxHeap($arr, 0, $heapSize);
    }
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
heapSort($arr);
$len = count($arr);
if($len % 2 == 0){
    $middle = ($arr[$len/2-1] + $arr[$len/2])/2;
}else{
    $middle = $arr[($len-1)/2];
}
echo "中数为：".$middle;

Summary

위는 PHP에서 순서가 지정되지 않은 배열의 중간 숫자를 찾는 두 가지 방법입니다. 시간 복잡도는 다르지만 모두 정렬되지 않은 배열을 빠르게 정렬하고 중앙값을 찾는 기능을 구현할 수 있습니다. 정렬되지 않은 다수의 배열을 정렬하여 중앙값을 구해야 한다면 시간 복잡도 성능이 더 좋은 힙 정렬 알고리즘을 사용하는 것이 좋습니다.

위 내용은 PHP에서 정렬되지 않은 배열에서 중앙값을 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!