JavaScript 정렬 알고리즘 구현

머리말
정렬 알고리즘 은 필기시험 에서 자주 나타 나 는 것 으로 정렬 알고리즘 을 제기 할 때 반드시 알고리즘 의 복잡 도와 대 O 표현법 을 제시 해 야 한다. 문장 알고리즘 의 복잡 도와 대 O 표현법 을 참고 할 수 있다.
거품 정렬
거품 정렬 의 공간 복잡 도 는 0 (n) 이다.²) 。실행 시간 으로 볼 때 거품 정렬 은 정렬 알고리즘 중 가장 효율 이 떨 어 지 는 것 입 니 다. 거품 정렬 은 두 개의 인접 한 항목 을 비교 하 는 것 입 니 다. 첫 번 째 가 두 번 째 보다 크 면 교환 합 니 다. 요 소 를 올 바른 순서 로 위로 이동 하면 기포 가 표면 으로 올 라 가 는 것 처럼 거품 정렬 이 되 어 이름 을 얻 었 습 니 다.

   	function bubbleSort(arr) {
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {
            swap(arr, j, j + 1)
          }Ï
        }
      }
    }

정렬 선택
정렬 의 복잡 도 를 O (n 으로 선택 하 십시오.²)。정렬 을 선택 하 는 것 은 거품 정렬 과 마찬가지 로 장 착 된 두 순환 을 포함 하여 2 차 측의 복잡 도 를 초래 합 니 다. 정렬 알고리즘 을 선택 하 는 것 은 원래 의 주소 비교 정렬 알고리즘 입 니 다. 정렬 을 선택 하 는 것 은 대체적으로 데이터 구조 에서 가장 작은 값 을 찾 아 첫 번 째 에 두 는 것 입 니 다. 이 어 두 번 째 작은 값 을 찾 아 두 번 째 에 두 는 것 입 니 다.

 function swap(arr, a, b) {
      let temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
      return arr
    }

    function selectSort(arr) {
      for (let i = 0; i < arr.length - 1; i++) {
        let min = arr[i];
        let minIndex = i;
        for (let j = i; j < arr.length; j++) {
          if (min > arr[j]) {
            min = arr[j];
            minIndex = j;
          }
        }
        swap(arr, i, minIndex)
      }
    }

삽입 정렬
정렬 알고리즘 을 삽입 하 는 복잡 도 는 O (n) 입 니 다.²) 。정렬 할 때마다 배열 항목 을 삽입 하여 마지막 정렬 배열 을 구축 합 니 다. 정렬 의 핵심 사상 은 부분 적 으로 변 합 니 다. 작은 배열 을 정렬 할 때 이 알고리즘 은 정렬 과 거품 정렬 을 선택 하 는 것 보다 성능 이 좋 습 니 다.

        function insertSort(arr) {
            var len = arr.length;
            var j, temp;
            for (var i = 1; i < len; i++) {
                j = i;
                temp = arr[i];
                while (i > 0 && arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = temp
            }
            return arr;
        }

빠 른 정렬
빠 른 정렬 시간 복잡 도 는 O (nlog ^ n) 이 며 성능 이 좋 습 니 다. 빠 른 정렬 은 분할 방법 으로 원본 배열 을 작은 배열 로 나 눕 니 다.

function quickArr(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var left = [],
        right = [];
    var pIndex = Math.floor(arr.length / 2);
    var p = arr.splice(pIndex, 1)[0];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= p) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    //   
    return quickArr(left).concat([p], quickArr(right));
}

힐 정렬
힐 정렬 은 정렬 을 삽입 하 는 효율 적 인 개선 판 이다.
이상 은 비교적 중요 하고 면접 에서 흔히 볼 수 있 는 몇 가지 정렬 알고리즘 입 니 다.
정렬
더미 정렬
계수 정렬
통 정렬
기수 정렬 (분산 정렬)