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

이 기사에서는 주로 PHP 정렬 알고리즘 시리즈 Merge Sort의 관련 정보를 자세히 소개합니다. 관심 있는 친구는

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 중국어 웹사이트를 응원해 주시길 바랍니다.

관심을 가질 만한 기사:

PHP 정렬 알고리즘 시리즈의 직접 선택 정렬에 대한 자세한 설명

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

버킷의 PHP 구현 정렬 알고리즘 설명

위 내용은 PHP 정렬 알고리즘 series_php 기술의 병합 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!