집 >백엔드 개발 >PHP 튜토리얼 >PHP 정렬 알고리즘 시리즈의 병합 정렬에 대한 자세한 설명

PHP 정렬 알고리즘 시리즈의 병합 정렬에 대한 자세한 설명

jacklove원래의: 2018-05-22 17:37:051865검색

이 글에서는 PHP 정렬 알고리즘 시리즈 중 병합 정렬에 대해 자세히 설명합니다.

Merge Sort

Merge Sort(MERGE-SORT)는 병합 작업을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 및 정복 방법(Divide and Conquer)의 매우 일반적인 응용 프로그램입니다. 이미 정렬된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 순서대로 만든 다음 하위 시퀀스 세그먼트를 순서대로 만듭니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다.

병합 과정

병합 정렬의 핵심은 두 개의 정렬된 배열이 있다고 가정합니다. 두 개의 정렬된 배열 중 첫 번째 요소를 비교하여 해당 요소를 병합합니다. 그것을 가져온 후에는 해당 배열에서 요소가 삭제되며, 배열에 요소가 없으면 다른 배열의 나머지 요소를 세 번째 배열에 직접 추가할 수 있습니다.

Principle

1. 시퀀스에서 인접한 두 숫자를 모두 병합하여 ceil(n/2) 시퀀스를 형성합니다. 정렬 후 각 시퀀스에는 두 개의 요소가 포함되며 마지막 시퀀스에는 하나의 요소만 있을 수 있습니다.

2. 위의 시퀀스를 다시 병합하여 ceil(n/4) 시퀀스를 만듭니다. 각 시퀀스에는 4개의 요소가 포함되며 마지막 시퀀스에는 3개 이하의 요소만 있을 수 있습니다.

3. 모든 요소가 정렬될 때까지 2단계를 반복합니다.

예

배열 [53,89,12,6,98,25,37,92,5] 정렬

첫 번째 병합 후

(53,89),12,(6,98) ,( 25,37),(5,92)

두 번째 병합 후

(12,53,89),(6,25,37,98),(5,92)

세 번째 병합 후

( 6,12,25,37,53,89,98),(5,92)

네 번째 합병 이후

5,6,12,25,37,53,89,92,98

PHP 코드 구현

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$half=ceil($length/2);
 
$arr2=array_chunk($arr,$half);
 
$left=merge_sort($arr2[0]);
 
$right=merge_sort($arr2[1]);
 
while(count($left)&&count($right)){
 
if($left[0]<$right[0]){
 
$reg[]=array_shift($left);
 
}else{
 
$reg[]=array_shift($right);
 
}
 
}
 
return array_merge($reg,$left,$right);
 
}

이 글은 PHP 정렬 알고리즘 시리즈 중 병합 정렬에 대한 자세한 설명을 설명하고 있습니다. 관련 내용은 PHP 중국어 홈페이지를 참고해주세요.

PHP 정렬 알고리즘 시리즈의 병합 정렬에 대한 자세한 설명

관련 기사