JS는 병합 정렬을 구현합니다.

이 글에서는 주로 참조값이 있는 JS 병합 정렬을 소개합니다. 이제 모든 사람과 공유합니다. 도움이 필요한 친구들이 참조할 수 있습니다.

재귀 메모리 스택 분석

저는 재귀를 깊이 이해한 적이 없습니다. 그 재귀 과정은 매우 추상적이며, 메모리 스택의 반환 과정을 명확하게 분석할 수 없습니다. 우연히 재귀에 대한 블로그 게시물을 접하게 되었고(기술적인 문제에는 여전히 더 많은 Google이 필요하다고 말하고 싶습니다) 재귀 프로세스의 메모리 스택 분석에 대해 갑자기 깨달았습니다. 분석 프로세스는 다음과 같습니다.

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test <p> 다음 그림은 전체 재귀를 정확하게 나열합니다. 이 과정에서 나중에 단일 재귀 문제가 발생하면 이 방법을 사용하여 분석할 수 있습니다. (여러 재귀의 경우 병합 정렬에서 두 재귀를 그리려고 시도하지만 정말 깔끔하게 타이핑할 방법이 없으니 포기하세요...) </p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg" class="lazy" title="1530956481159780.jpg" alt="JS는 병합 정렬을 구현합니다."> </p>
<p>본론으로 돌아가 병합과 정렬을 분석해 보겠습니다. </p>
<h3 id="Merge-sort">Merge sort</h3>
<p>Merge sort는 분할 및 정복이라는 아이디어를 채택합니다. 첫 번째는 각 배열에 하나의 요소만 있을 때까지 배열을 두 개의 작은 배열로 반복적으로 나누는 것입니다. 가장 작은 배열부터 각 쌍을 크기 순서대로 병합하여 원래 배열 크기로 병합합니다. 다음은 그림입니다. </p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png" class="lazy" title="1530956488945859.png" alt="JS는 병합 정렬을 구현합니다."></p>
<p> 실제로 "통제"하는 과정을 관찰해 보세요. 더 큰 순서의 배열을 위해 이미 순서가 지정된 배열을 병합하는 것을 의미합니다. 그렇다면 이미 정렬된 배열을 더 큰 정렬된 배열로 병합하는 방법은 무엇입니까? 매우 간단합니다. 임시 배열 C를 만들고 A[0], B[0]을 비교하고 더 작은 값을 C[0]에 넣은 다음 A[1]과 B[0](또는 A[0], B [1]), A와 B가 한 번 통과할 때까지 C[1]에 더 작은 값을 입력합니다. 배열 A와 B는 한 번만 순회하면 되므로 두 개의 정렬된 배열을 정렬하는 시간 복잡도는 O(n)입니다. </p>
<p>그리고 "나누기"는 각 배열에 하나의 요소만 남을 때까지 원래 배열을 두 부분으로 차례로 나누는 것입니다. 단일 요소 배열은 자연스럽게 순서가 지정되므로 "치료" 과정이 시작될 수 있습니다. </p>
<p>시간 복잡도 분석: 나누기 프로세스에는 세 단계가 필요합니다: log8 = 3, 각 단계는 8개 요소를 한 번 통과해야 하므로 총 8개 요소를 실행해야 합니다. 8log8) 명령, n개 요소에 대한 시간 복잡도는 다음과 같습니다. 오(nlogn). </p>
<p>코드는 두 가지 재귀를 사용하는데, 이는 매우 추상적이고 이해하기 어렵습니다. 그것을 알아내는 데 전체 스택 호출 다이어그램이 걸렸습니다(너무 지저분해서 게시하지 않겠습니다). </p>
<pre class="brush:php;toolbar:false">// 融合两个有序数组，这里实际上是将数组 arr 分为两个数组
function mergeArray(arr, first, mid, last, temp) {
  let i = first; 
  let m = mid;
  let j = mid+1;
  let n = last;
  let k = 0;
  while(i<p>위 내용은 모두의 학습에 도움이 되기를 바랍니다. 더 많은 관련 내용은 PHP 중국어 홈페이지를 주목해주세요! </p><p>관련 권장 사항: </p><p><a title="JS实现希尔排序" href="http://www.php.cn/js-tutorial-406221.html" target="_blank">JS는 Hill 정렬을 구현합니다</a><br></p><p><a title="Jquery添加loading过渡遮罩" href="http://www.php.cn/js-tutorial-406220.html" target="_blank">Jquery는 로딩 전환 마스크를 추가합니다</a><br></p>

위 내용은 JS는 병합 정렬을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!