PHP 정렬 알고리즘 의 병합 정렬(Merging Sort)실례 상세 설명

이 실례 는 PHP 정렬 알고리즘 의 병합 정렬(Merging Sort)을 설명 한다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
기본 사상:
병합 정렬:병합(합병)의 사상 을 이용 하여 정렬 하 는 방법 이다.그 원 리 는 초기 서열 에 n 개의 요 소 를 포함 하고 있다 고 가정 하면 n 개의 질서 있 는 하위 서열 로 볼 수 있다.각 하위 서열 의 길 이 는 1 이 고 두 개의 병합 을 통 해 전체 8968°n/2*8969°(*8968°x*8969°x 보다 작 지 않 은 최소 정수)개의 길 이 는 2 또는 1 의 질서 있 는 서열 을 얻 을 수 있다.두 번 더 합치 면.................................................................................
1.병합 의 과정:
a[i]a 배열 의 앞부분(순서 가 정 해 져 있 음),a[j]a 배열 의 뒷부분(순서 가 정 해 져 있 음)
r 배열 은 정렬 된 a 배열 을 저장 합 니 다.
a[i]와 a[j]의 크기 를 비교 하고 a[i]≤a[j]라면 첫 번 째 질서 표 의 요소 a[i]를 r[k]에 복사 하고 i 와 k 를 각각 1 로 추가 합 니 다.그렇지 않 으 면 두 번 째 질서 표 의 요소 a[j]를 r[k]에 복사 하고 j 와 k 를 각각 1 을 더 해서 그 중의 질서 표 가 끝 날 때 까지 순환 한 다음 에 다른 질서 표 의 나머지 요 소 를 r 에서 아래 표 k 에서 아래 표 t 의 단원 으로 복사 합 니 다.정렬 을 병합 하 는 알고리즘 은 보통 재 귀적 으로 이 루어 집 니 다.먼저 정렬 대기 구간[s,t]을 중심 점 2 점 으로 나 눈 다음 에 왼쪽 부분 구간 을 정렬 한 다음 에 오른쪽 부분 구간 을 정렬 하고 마지막 으로 왼쪽 구간 과 오른쪽 구간 을 한 번 에 병합 하여 질서 있 는 구간[s,t]으로 합 칩 니 다.
2.병합 작업:
병합 작업(merge)은 병합 알고리즘 이 라 고도 하 는데 두 순서 서열 을 하나의 순서 서열 로 합 치 는 방법 을 말한다.
수열{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},비교 횟수:4;
세 번 째 병합 후:{1,6,8,38,100,202,301},비교 횟수:4;
총 비교 횟수 는:3+4+4=11,;
역순 수 는 14 이다.
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()함 수 는 배열 을 반 으로 나 누 어 반 으로 나 눈 다음 에 하위 서열 의 길 이 를 1 로 나 눈 다음 에 하위 서열 을 합 친다.
지금 은 우리 의 병합 조작 함수 입 니 다Merge():

//    
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];
  }
}

여기까지 오 면 우리 의 병합 알고리즘 은 끝장 이다.우리 호출 해 보 자:

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

복잡 도 분석:
병합 알고리즘 은 원래 의 서열 이 질서 가 있 든 없 든 그룹 을 나 누고 비교 하기 때문에 가장 좋 고 최 악의 시간 복잡 도 는 모두 O(nlogn)이다.
병합 알고리즘 은 안정 적 인 정렬 알고리즘 이다.
본 고 는 을 참고 하여 여기 서 기록 만 하고 나중에 조회 하기에 편리 하 며 큰 신 은 뿌리 지 마 세 요!
PS:정렬 에 관 한 프 리 젠 테 이 션 도 구 를 추천 합 니 다.참고 하 시기 바 랍 니 다.
온라인 애니메이션 프레젠테이션 삽입/선택/거품/병합/힐/빠 른 정렬 알고리즘 프로 세 스 도구:
대화 데이터 구조
더 많은 PHP 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.