우리는 이미 기본적인 정렬 알고리즘을 완성했다!거품 정렬, 선택 정렬, 삽입 정렬은 이해하기 쉽고 이해하기 쉽다.시간의 추이에 따라 이러한 목표를 실현하는 것은 자연스러운 것이다.솔직히 이 기본 알고리즘들은 단점이 있다. 확장이 잘 안 된다.입력한 크기를 배로 늘리면 정렬 그룹을 만드는 시간을 배로 늘립니다!
따라서 우리는 더 높은 알고리즘으로 전환할 것이다. 그것들의 정렬 시간은 O (nlog (n) 이다.더 말할 것도 없이, 첫 번째 효율적인 자바스크립트 정렬 알고리즘인 통합 정렬을 소개합니다.

병합 정렬 소개

우리가 본 정렬 알고리즘에 비해 통합 정렬은 완전히 다르다.병합 정렬은 시작 그룹을 0 또는 1 요소의 작은 그룹으로 나누어 다시 병합합니다.어레이에서 두 번 순환할 필요가 없습니다!
전체 과정은 두 가지 주요 절차가 있다.

을 수조로 나누다

작은 어레이를 결합한

형상화

이 알고리즘의 입력은 [38, 1, 40, 34, 9, 41, 2, 16]이다.📊

비주얼고를 사용하여 정렬을 시각화합니다.방문하십시오.https://visualgo.net/더 많은 시각 알고리즘.
작업량이 많아 보이죠?그러나 사실은 그렇지 않다. 우리는 단지 수조 (컬러 요소) 를 분할한 후에 원소를 한데 합칠 뿐이다.우선 합병 논리를 알아보자.알고리즘 중의 어떤 점에서 우리는 반드시 아래의 자진열인 [[1, 38], [34, 40]]을 합병해야 한다.이 두 요소는 모두 정렬되었습니다. 이것은 새로운 정렬 그룹을 만드는 필수 조건입니다. 이 그룹은 이 두 개의 하위 그룹에서 찾은 모든 요소를 포함합니다.

합병 실현

병합 정렬의 위조 코드입니다.

빈 그룹을 만들고 색인 i와 j를 만듭니다

, 그러나 여전히 일부 가치관을 우리는 보지 못했다.만약 첫 번째 그룹의 값이 두 번째 그룹의 값보다 작다면, 우리는 이 값을 빈 그룹에 밀어 넣고, i의 값을 증가한 다음, 첫 번째 그룹의 다음 값 2로 넘어갈 것이다.그렇지 않으면, 만약 두 번째 수조의 값이 첫 번째 수조의 값보다 작다면, 우리는 이 값을 빈 수조로 밀어내고 j의 값을 증가한 다음에 두 번째 수조의 다음 값인

으로 돌릴 것이다

한 수조의 모든 원소가 정렬 수조로 전송될 때 우리는 두 번째 수조의 모든 나머지 원소도 정렬 수조

으로 전송할 것이다

function merge(arr1, arr2) {
  let results = [];

  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  console.log(results);
  return results;
}

[[1,38],[34,40]]을 입력하는 것을 예로 삼아 코드를 훑어보고 여기에 무슨 일이 일어났는지 봅시다.순환을 실행하기 전에, 우리는 빈 그룹과 두 개의 인덱스를 만들었습니다.색인 i와 j의 값과 합칠 두 그룹의 길이보다 작은지 순환적으로 검사합니다.만약arr1의 인덱스 i에 있는 요소가arr2의 인덱스 j에 있는 요소보다 작다면, 우리는 이 요소를 결과 그룹에 전송할 것입니다.
우리의 예시적인 수조를 고려하여 우리는 인덱스 0과 0의 값, 즉 1과 34를 비교하였기 때문에 우리는 1을 결과수조로 미루고 i의 값을 증가시켰다. 다음 번에는 인덱스 1과 0을 비교하였는데, 지금은 38과 34이고, 34가 38보다 작다는 것을 고려하여 34를 결과수조(지금은 [1,34])로 미루었다.우리는 j의 값을 증가시켰다. 최종 정렬된 그룹을 얻을 때까지 이 과정을 반복했다.

병합 정렬 구현

이 솔루션은 recursion을 사용합니다.이전에 귀속 코드를 사용한 적이 없는 프로그래머는 귀속이 직관적이지 않다는 것을 발견할 수 있으며, 링크를 검사해서 이 개념을 더욱 잘 이해하는 것이 좋은 생각일 수도 있다.
병합 정렬의 위조 코드는 다음과 같습니다.

알고리즘은 원소를 포함하지 않거나 한 원소만 포함하는 수조를 생성할 때까지 수조를 반으로 줄일 것이다

이 이 수조가 존재하면 알고리즘은 이 수조(상기 방법을 사용)를 합병하여'합병'수조의 길이가 시작 수조

의 길이와 같을 때까지 합병한다.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  } else {
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
  }
}

알칼리기는 수조의 길이가 1 또는 0이면 우리는 수조로 되돌아간다. 그렇지 않으면 우리는 중간의 원소를 상자에 넣은 다음에 수조를 왼쪽, 오른쪽 두 개의 자수조로 나누고, 마지막으로 이 두 개의 수조에merge를 호출한다.
이제 시각화를 되돌아봅시다.
매우 편리합니다. 우리의 수조에는 8개의 원소가 있습니다.이 알고리즘은 먼저 수조를 4개로 나눈 다음에 2개로 나눈 다음에 원소 서브수조로 나눈다.어떤 점에서 원소는 모두 다른 색깔이다. 이것은 원소가 독립적이라는 것을 의미한다.그 다음에 알고리즘은 원소를 다시 합치기 시작한다. 38과 1은 [1,38], 40과 34는 [34,40]로 변하고 이 두 개의 수조는 합쳐져 모든 원소가 정렬될 때까지 알고리즘이 운행된다.

대O 복잡성

병합 정렬의 최적 상태, 평균 상태와 최악의 상황은 모두 같다. - O(nlog(n)).Log (n) 는 알고리즘에서 반드시 수행해야 하는 분할 수에서 나온다.8개의 요소를 보유하고 있다는 것은 어레이를 세 배로 줄여야 한다는 것을 의미한다.

은 처음에 2개의 어레이를 제공했습니다. 어레이당 4개의 요소인

두 번째 어레이에는 2개의 요소인

의 4개의 어레이가 포함됩니다.

세 번째 어레이에는 각각 하나의 요소인

의 8개의 어레이가 포함됩니다.
만약 우리가 입력 수조의 크기를 배로 늘린다면, 우리는 알고리즘에 제법을 추가해야 한다.공식의 n은 수조를 다시 합칠 때 진행되는 비교 횟수입니다.

결론

이것은 우리의 네 번째 자바스크립트 정렬 알고리즘 문장입니다. 통합 정렬을 포함합니다!기본적인 세 개보다 전면적이지만 이해하기 쉬워요. 그렇죠?!만약 당신이 이것을 좋아한다면, 전체 시리즈를 검사하거나, 나의 blog 더 많은 과학 기술 문장을 방문하십시오.