PHP 정렬 알고리즘 Merging Sort(머징 정렬)

이 글에서는 주로 PHP 정렬 알고리즘의 Merging Sort를 소개하며, PHP Merging Sort의 원리, 정의, 사용 방법 및 관련 동작 주의 사항을 예제와 함께 자세히 분석합니다. PHP 정렬 알고리즘의 Merging Sort. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

기본 아이디어: 병합 정렬: 병합(병합)이라는 아이디어를 사용하여 구현된 정렬 방법입니다. 그 원리는 초기 시퀀스에 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 < $end){
    $mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
    MSort($arr,$start,$mid);  //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
    MSort($arr,$mid + 1,$end);  //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
    Merge($arr,$start,$mid,$end);    //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  }
}

MSort() 函数：

//归并操作
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<=$end; $i++){
    $arr[$i] = $temparr[$i];
  }
}

上面的 MSort() 函数实现将数组分半再分半（直到子序列长度为1），然后将子序列合并起来。

现在是我们的归并操作函数 Merge()

위의 MSort() 함수는 배열을 반으로 나눈 다음 반으로 나누는 것을 구현합니다. (하위 시퀀스 길이가 1이 될 때까지) 그런 다음 하위 시퀀스가 ​​결합됩니다.

이제 병합 작업 함수 Merge()입니다.

$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)

입니다.

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

이 기사는 "Dahua 데이터 구조"를 참조했습니다. 나중에 참고할 수 있도록 여기에만 기록했습니다. 관련 추천:

PHP 정렬 알고리즘 버블 정렬

PHP 정렬 알고리즘 단순 선택 정렬

PHP 정렬 알고리즘 직선 삽입 정렬 )

🎜🎜🎜🎜

위 내용은 PHP 정렬 알고리즘 Merging Sort(머징 정렬)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!