JavaScript는 삽입 종류의 고전적인 정렬 알고리즘을 구현합니다.-JS 튜토리얼-php.cn

JavaScript는 삽입 종류의 고전적인 정렬 알고리즘을 구현합니다.

高洛峰

풀어 주다： 2016-12-29 15:59:38

원래의

1485명이 탐색했습니다.

삽입 정렬의 코드 구현은 버블 정렬 및 선택 정렬만큼 간단하고 투박하지는 않지만 포커를 해본 사람이라면 누구나 몇 초 안에 이해할 수 있어야 하기 때문에 그 원리는 가장 이해하기 쉬워야 합니다. 포커 패를 분류하는 것처럼 우리는 왼손을 비우고 테이블 위의 카드가 아래를 향하도록 시작합니다. 그런 다음 매번 테이블에서 카드 한 장을 가져와 왼손의 올바른 위치에 삽입합니다. 카드의 올바른 위치를 찾기 위해 이미 손에 있는 모든 카드를 오른쪽에서 왼쪽으로 비교합니다. 왼손에 들고 있는 카드는 항상 정렬되어 있으며 원래는 테이블 더미의 맨 위에 있는 카드였습니다.

1) 알고리즘 원리

삽입 정렬(Insertion-Sort)의 알고리즘 설명은 간단하고 직관적인 정렬 알고리즘입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 추가 공간만 사용하는 정렬)이 사용되므로 스캔 과정에서 뒤에서 앞으로 반복적이고 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.

2) 알고리즘 설명 및 구현

일반적으로 삽입 정렬은 in-place를 사용하여 배열에 구현됩니다. 구체적인 알고리즘은 다음과 같습니다.

<1> 첫 번째 요소부터 정렬된 것으로 간주할 수 있습니다.

<2> 정렬된 요소 이후 순서대로

<3> 정렬된 요소가 새 요소보다 큰 경우 해당 요소를 다음 위치로 이동합니다. <4> 3단계를 반복합니다. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지

<5>

<6> 2~5단계를 반복합니다.

3) JavaScript 코드 구현

삽입 정렬 개선: 삽입 위치를 찾을 때 이진 검색을 사용합니다.

function insertSort(arr) { 
    for (var i = 1; i < arr.length; i++) { 
      var temp = arr[i]; 
      var j = i - 1; 
      while (j >= 0 && arr[j] > temp) { 
        arr[j + 1] = arr[j]; 
         j--; 
      } 
      arr[j + 1] = temp; 
    } 
    return arr; 
 } 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(insertSort(arr));

로그인 후 복사

단계:
이진 검색은 시퀀스에서 숫자보다 큰 첫 번째 숫자의 위치를 찾습니다.

이 위치에 새 요소가 삽입됨; >

최고 경우: 입력 배열이 오름차순으로 정렬됩니다. T(n) = O(n)
최악의 경우: 입력 배열이 내림차순으로 정렬됩니다. T(n) = O(n2)
평균 상황: T(n) = O(n2)

위 내용이 모두의 학습에 도움이 되기를 바랍니다. 나는 또한 모든 사람들이 PHP 중국어 웹사이트를 더 많이 배우기를 바랍니다.

function binaryInsertionSort(arr) { 
   for (var i = 1; i < arr.length; i++) { 
     var key = arr[i],left = 0,right = i - 1; 
     while (left <= right) { 
        var middle = parseInt((left + right) / 2); 
        if (key < arr[middle]) { 
          right = middle - 1; 
        } else { 
          left = middle + 1; 
        } 
     } 
     for (var j = i - 1; j >= left; j--) { 
        arr[j + 1] = arr[j]; 
     } 
     arr[left] = key; 
    } 
    return arr; 
} 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(binaryInsertionSort(arr));

로그인 후 복사

JavaScript를 사용하여 고전적인 정렬 알고리즘을 구현한 삽입 정렬과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!