JavaScript의 병합 정렬에 대한 자세한 설명

이 기사에서는 JavaScript의 병합 정렬에 대해 설명합니다. JavaScript의 병합 정렬에 대해 모르거나 JavaScript의 병합 정렬에 관심이 있다면 이 기사를 살펴보겠습니다.

JavaScript의 병합 정렬

분할 정복 아이디어의 일반적인 알고리즘 응용으로 병합 정렬은 두 가지 방법으로 구현됩니다.

1. 하향식 재귀(모든 재귀 방법은 반복으로 다시 작성할 수 있음) 그래서 두 번째 방법이 있습니다)

2. 상향식 반복

"데이터 구조 및 알고리즘 JavaScript 설명"에서 저자는 상향식 반복 방법을 제공합니다. 하지만 재귀적 방법에 대해 저자는 다음과 같이 생각합니다.

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

솔직히 이 문장을 잘 이해하지 못합니다. JavaScript 컴파일러의 메모리가 너무 작고 재귀가 너무 깊어서 메모리 오버플로가 쉽게 발생할 수 있다는 뜻인가요? 누군가가 나에게 조언을 해줄 수 있기를 바랍니다.

선택 정렬과 마찬가지로 병합 정렬의 성능은 입력 데이터의 영향을 받지 않지만 시간 복잡도가 항상 O(n log n)이기 때문에 선택 정렬보다 성능이 훨씬 좋습니다. 가격은 추가 메모리 공간입니다.

머지 정렬 애니메이션 데모

머지 정렬 JavaScript 코드 구현:

function mergeSort(arr) {  //采用自上而下的递归方法  
   var len = arr.length;  
   if(len < 2) {  
       return arr;  
   }  
   var middle = Math.floor(len / 2),  
       left = arr.slice(0, middle),  
       right = arr.slice(middle);  
   return merge(mergeSort(left), mergeSort(right));}function merge(left, right){  
   var result = [];  
  
   while (left.length && right.length) {  
       if (left[0] <= right[0]) {  
           result.push(left.shift());  
       } else {  
           result.push(right.shift());  
       }  
   }  
  
   while (left.length)  
       result.push(left.shift());  
  
   while (right.length)  
       result.push(right.shift());  
  
   return result;}

위 내용은 이 글의 내용 전부입니다. 잘 모르시면 양쪽 모두 직접 구현하셔도 됩니다. 마스터하기 쉽다!

관련 추천:

흥미로운 JavaScript 질문: 연결 목록의 병합 정렬

JavaScript는 연결 목록 삽입 정렬과 연결 목록 병합 정렬을 구현합니다

위 내용은 JavaScript의 병합 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!