JavaScript의 병합 정렬 소개(코드 예)

이 글은 JavaScript의 병합 정렬(코드 예제)에 대한 소개를 제공합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

병합 정렬(MERGE-SORT)은 병합 연산을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 정복 방법(pide)을 사용합니다. andConquer)는 매우 일반적인 애플리케이션입니다. 이미 정렬된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 순서대로 만든 다음 하위 시퀀스 세그먼트를 순서대로 만듭니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다.

Merge sort

Merge sort는 매우 안정적인 정렬 방법으로 평균, 최고, 최악의 시간 복잡도가 NlogN입니다.

2단계 병합 정렬

1. 첫 번째 분할, 숫자가 하나만 있을 때까지

2. 분할이 완료된 후 재귀적 병합을 시작합니다

분할 프로세스

From As 위 그림에서 볼 수 있듯이 병합 정렬은 배열을 두 쌍으로 분할하고 숫자가 하나만 있으면 분할을 중지합니다.
그러면 분할 코드는 매우 간단합니다. 즉, 중앙을 가리키는 포인터 q를 얻고 배열을 (시작, p)와 (p, 끝)의 두 부분으로 분할하는 것입니다.

• p는 배열의 시작 첨자를 나타냅니다.

• r은 배열의 끝 첨자를 나타냅니다.

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

병합 과정

병합 과정은 위 그림과 같습니다

1. 릴리앙 그룹 데이터

2. 크기 비교

3. 더 작은 값을 빼서 첫 번째 위치에 배치합니다

예:

• 배열 A의 현재 데이터가 [2 ,5, 1,3]

• 분할 후에는 (0,2),(2,4);

• A.slice(0,2) 및 A.slice(2를 전달합니다. ,4 )=>두 개의 배열 A1[2,5] 및 A2[1,3]을 가져옵니다

• 그런 다음 배열 [2,5,1,3]을 탐색하고 처음으로 더 작은 배열을 얻습니다. 양쪽에 1을 세고, 두 번째는 2, 세 번째는 3, 네 번째는 5

    function merge(A, p, q, r){
        const A1 = A.slice(p, q);
        const A2 = A.slice(q, r);
        
        // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
        
        A1.push(Number.MAX_SAFE_INTEGER);
        A2.push(Number.MAX_SAFE_INTEGER);
        // 循环做比较，每次取出较小的那个值
        for (let i = p, j = 0, k = 0; i <h3 id="메인-프로그램">메인 프로그램</h3><p>메인 프로그램은 위의 연산을 재귀적으로 반복하는 것입니다</p><pre class="brush:php;toolbar:false">    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

완성 코드

rreee

위 내용은 JavaScript의 병합 정렬 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!