집 > 기사 > 백엔드 개발 > PHP 정렬 알고리즘의 병합 정렬에 대한 자세한 설명

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

小云云원래의: 2018-01-08 09:54:161559검색

PHP 정렬 알고리즘에는 여러 종류가 있습니다. 이 글에서는 주로 PHP 정렬 알고리즘 시리즈 병합 정렬에 대한 관련 정보를 소개합니다. 관심 있는 친구들이 참고할 수 있기를 바랍니다.

Merge Sort

Merge Sort(MERGE-SORT)는 병합 작업을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 및 정복 방법(pide 및 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)

번째 3번째 이후 병합

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

네 번째 병합 후

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

PHP 코드 구현

<?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 정렬 알고리즘의 병합 정렬에 대한 자세한 설명

관련 기사