PHP에서 병합 정렬을 구현하는 방법

PHP에서 병합 정렬을 구현하는 방법: 1. PHP 샘플 파일을 만듭니다. 2. "public function handler(){...}" 메서드를 정의합니다. 3. "private function mergeSort($a, $lo, $ hi) {...}" 방식으로 데이터를 점진적으로 분해합니다. 4. 분해된 데이터를 정렬한 후 병합하려면 "merge" 방식을 사용합니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, PHP 버전 8.1, Dell G3 컴퓨터.

php는 병합 정렬 알고리즘을 구현합니다

병합 정렬 알고리즘의 복잡도는 O(nlogn)입니다.

코드는 다음과 같습니다. 복제하고 실행하기만 하면composer install然后执行 php artisan test:mergeSort 결과를 볼 수 있습니다

    /**
     * 归并排序把数据逐步分解，然后对分解后的数据进行排序，最后合并到一起
     *
     * @return mixed
     */
    public function handle()
    {
        $this->a = [3,70,4,38,5,6,8,4,7,10,6,10,34,4];
        dump($this->a);
        $a = $this->mergeSort($this->a, 0, count($this->a));
        dd($a);
    }
    private function mergeSort($a, $lo, $hi) {
        if (($hi - $lo) < 2) return [$a[$lo]];
        $mi = ($lo + $hi) >> 1;
        //把中点左边的进行归并
        $b = $this->mergeSort($a, $lo, $mi);
        dump(&#39;$b:&#39;,$b);
        //把中点右边的进行归并
        $c = $this->mergeSort($a, $mi, $hi);
        dump(&#39;$c:&#39;,$c);
        //把所有数据进行排序
        return $this->merge($b, $c, $lo,$mi,$hi);
    }
    /**
     * 假设有一个数组$a分成了两个数组[3,4] [2,8]
     * 逐一比较，3and2，取出来2然后3and8取出来3然后4and8取出来4，最后取出来8
     *
     * @param [type] $lo
     * @param [type] $mi
     * @param [type] $hi
     * @return void
     */
    private function merge($b, $c, $lo, $mi, $hi) {
        $lb = $mi - $lo; //$b数组的边界
        $lc = $hi - $mi; //$c数组的边界
        $res = [];
        //$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标 
        for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
            //ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素，那么取出来b的首元素
            if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
                $res[$i++] = $b[$ib++];
            }
            //k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出来c的首元素 
            if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
                $res[$i++] = $c[$ic++];
            }
        }
        return $res;
    }

병합 정렬의 원리

병합 정렬은 퀵 정렬의 반대입니다. 먼저 전체 배열을 분할합니다. 마지막으로 전체 배열의 정렬을 완료합니다.

먼저 전체 배열을 왼쪽과 오른쪽으로 분산시켜서 배열을 만듭니다. 단일 요소 - 단일 요소는 순서가 지정된 것으로 간주될 수 있기 때문입니다.

해당 코드

if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中点左边的进行归并
$b = $this->mergeSort($a, $lo, $mi);
dump(&#39;$b:&#39;,$b);
//把中点右边的进行归并
$c = $this->mergeSort($a, $mi, $hi);
dump(&#39;$c:&#39;,$c);

다음으로 두 개의 배열을 왼쪽과 오른쪽으로 정렬해 두 개의 배열 [3,4] [2,8]로 나누어진 배열 $a가 있다고 가정하고, 하나씩 비교해 보세요. 3and2, 그리고 2를 꺼내세요. 그런 다음 3and8을 빼고, 3을 빼고, 4and8을 빼고, 4를 빼고, 마지막으로 8을 꺼냅니다. 해당 코드:

$lb = $mi - $lo; //$b数组的边界
$lc = $hi - $mi; //$c数组的边界
$res = [];
//$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标 
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
    //ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素，那么取出来b的首元素
    if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
        $res[$i++] = $b[$ib++];
    }
    //k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出来c的首元素 
    if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
        $res[$i++] = $c[$ic++];
    }
}
return $res;

그림은 다음과 같습니다:

추천 학습: "PHP 비디오 튜토리얼"

위 내용은 PHP에서 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!