PHP에서 병합 정렬 알고리즘을 구현하는 단계에 대한 자세한 설명

이번에는 PHP에서 병합 정렬 알고리즘을 구현하는 단계에 대해 자세히 설명하겠습니다. PHP에서 병합 정렬 알고리즘을 구현하는 데 있어 주의 사항은 무엇입니까?

기본 아이디어:

병합 정렬: 병합(병합)이라는 아이디어를 이용하여 구현한 정렬 방법입니다. 그 원리는 초기 시퀀스에 n개의 요소가 포함되어 있다고 가정하면 n개의 정렬된 하위 시퀀스로 간주할 수 있으며, 각 하위 시퀀스의 길이는 1인 다음 쌍으로 병합되어 ⌈ n / 2⌉을 얻습니다(⌈ x ⌉는 가장 작은 것이 아님을 의미함). 양방향 병합 정렬보다 작은 정수.

1. 병합 과정:

a[i]는 a 배열의 앞부분을 차지하고(이미 정렬됨) a[j]는 a 배열의 뒷부분을 차지합니다(이미 정렬됨)

r 배열 저장 정렬된 배열

은 a[i]와 a[j]의 크기를 비교합니다. a[i] ≤ a[j]인 경우 첫 번째 순서 목록의 요소 a[i]를 r [k]에 복사합니다. i와 k에 각각 1을 추가하고, 그렇지 않으면 두 번째 순서 목록의 a[j] 요소를 r[k]에 복사하고 j와 k에 각각 1을 추가하는 식으로 계속합니다. 가져온 다음 다른 순서 목록의 나머지 요소를 아래 첨자 k에서 아래 첨자 t까지 r의 셀에 복사합니다. 우리는 병합 정렬 알고리즘을 구현하기 위해 일반적으로 재귀를 사용합니다. 먼저 정렬할 구간 [s, t]를 중간점에서 2개로 나누고, 왼쪽 하위 범위를 정렬한 다음, 오른쪽 하위 범위를 정렬하고, 마지막으로 a를 수행합니다. 왼쪽 및 오른쪽 간격에 대한 병합 작업을 순서 있는 간격 [s,t]로 병합합니다.

2. 병합 작업:

병합 알고리즘이라고도 불리는 병합 작업(병합)은 두 개의 순차 시퀀스를 하나의 순차 시퀀스로 병합하는 방법을 말합니다.

시퀀스 {6, 202, 100, 301, 38, 8, 1}이 있다고 가정합니다.

초기 상태: 6, 202, 100, 301, 38, 8, 1

첫 번째 병합 후: {6,202} ,{100,301},{8,38},{1}, 비교 횟수: 3;

두 번째 병합 후: {6,100,202,301}, {1,8,38}, 비교 횟수:

세 번째 병합 후: {1,6,8,38,100,202,301}, 비교 횟수: 4

총 비교 횟수: 3+4+4=11,

역방향 숫자는 14입니다.

3. 알고리즘 설명:

병합 작업의 작동 원리는 다음과 같습니다.

1단계: 크기가 정렬된 두 시퀀스의 합이 되도록 공간을 적용합니다. 이 공간은 병합된 내용을 저장하는 데 사용됩니다. 시퀀스

2단계: 두 개 설정 포인터의 초기 위치는 각각 정렬된 두 시퀀스의 시작 위치입니다.

3단계: 두 포인터가 가리키는 요소를 비교하고 상대적으로 작은 요소를 선택하여 병합에 넣습니다. 스페이스를 추가하고 포인터를 다음 위치로 이동합니다.

특정 포인터가 시퀀스의 끝을 초과할 때까지 3단계를 반복합니다.

다른 시퀀스의 나머지 모든 요소를 ​​병합된 시퀀스의 끝으로 직접 복사합니다.

알고리즘 구현:

먼저 주요 함수 부분을 살펴보겠습니다.

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//归并算法总函数
function MergeSort(array &$arr){
  $start = 0;
  $end = count($arr) - 1;
  MSort($arr,$start,$end);
}

전체 함수에서는 하나의 MSort() 함수만 호출했습니다. 우리는 재귀 호출을 사용하기 위해 MSort()를 캡슐화했습니다.

MSort() 함수를 살펴보겠습니다.

function MSort(array &$arr,$start,$end){
  //当子序列长度为1时，$start == $end，不用再分组
  if($start <code>MSort()</code> 函数：<pre class="brush:php;toolbar:false">//归并操作
function Merge(array &$arr,$start,$mid,$end){
  $i = $start;
  $j=$mid + 1;
  $k = $start;
  $temparr = array();
  while($i!=$mid+1 && $j!=$end+1)
  {
    if($arr[$i] >= $arr[$j]){
      $temparr[$k++] = $arr[$j++];
    }
    else{
      $temparr[$k++] = $arr[$i++];
    }
  }
  //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($i != $mid+1){
    $temparr[$k++] = $arr[$i++];
  }
  //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($j != $end+1){
    $temparr[$k++] = $arr[$j++];
  }
  for($i=$start; $i<p style="text-align: left;">上面的 <code>MSort()</code> 函数实现将数组分半再分半（直到子序列长度为1），然后将子序列合并起来。</p><p style="text-align: left;">现在是我们的归并操作函数 <code>Merge()</code>위의 <code>MSort()</code> 함수는 배열을 반으로 나눈 다음 반으로 나누는 것을 구현합니다(하위 시퀀스까지) 길이는 1 ), 하위 시퀀스를 병합합니다. </p><p style="text-align: left;">이제 병합 작업 함수 <code>Merge()</code>입니다.</p><pre class="brush:php;toolbar:false">$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);

이 시점에서 병합 알고리즘이 완성되었습니다. 호출해 봅시다:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

실행 결과: rrreee복잡성 분석:

병합 알고리즘은 원래 시퀀스의 순서 여부에 관계없이 그룹화하고 비교하므로 최고, 최악, 평균 시간 복잡성은

O(nlogn)

입니다.

병합 알고리즘은 안정적인 정렬 알고리즘입니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!

🎜추천 도서: 🎜

PHP 싱글톤 모드 사용 사례에 대한 자세한 설명

php+receivemail을 사용하여 이메일을 보내고 받음

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