전단 에서 파악 해 야 할 몇 가지 정렬 알고리즘

전에 면접 에서 빠 른 줄 을 물 었 고 어제 필기시험 에서 정렬 알고리즘 에 관 한 문 제 를 풀 었 기 때문에 정렬 알고리즘 에 관 한 문 제 를 특별히 보 았 습 니 다.전단 에서 알고리즘 에 대한 요구 가 높 지 않 지만 아래 의 이해 하기 쉬 운 정렬 알고리즘 은 파악 해 야 한다.
간단 한 소개 및 실현
아래 의 순 서 는 모두 오름차 순 이다.
거품 정렬
거품 정렬 은 가장 간단 한 정렬 이다. 즉, 앞 뒤 두 수의 크기 를 비교 하 는 것 이다.

function bubble(arr) {
  for(let i = 0, len = arr.length; i < len; i++) {
    for(let j = 0; j < len; j++) {
      if(arr[j] > arr[j + 1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  
  return arr;
}

정렬 선택
정렬 을 선택 하려 면 먼저 최소 값 을 선택해 야 합 니 다. 이 최소 값 을 뒤에 정렬 되 지 않 은 숫자 와 비교 하고 더 작 으 면 위 치 를 바 꿔 야 합 니 다.

function selection(arr) {
  let min;
  for(let i = 0, len =arr.length; i < len; i++) {
    min = arr[i];
    for(let j = i+1; j < len; j++) {
      if(arr[j] < min) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  
  return arr;
}

삽입 정렬
정렬 원 리 를 삽입 하 는 것 과 포커 를 칠 때 카드 를 순서대로 삽입 하 는 것 은 차이 가 많 지 않다. 두 번 째 카드 부터 앞 을 보면 숫자 가 두 번 째 카드 보다 작은 지, 처리 한 후에 세 번 째 카드 를 보면 이런 식 으로 유추 하면 n 번 째 카드 에서 n 앞 에 있 는 카드 가 n 번 째 위치 에 있 는 카드 보다 작은 지 여 부 를 볼 수 있다.

function insert(arr) {
  for(let i = 1, len = arr.length; i < len; i++) {
    let target = arr[i];
    for(let j = i; j >=0; j--) {
      if(arr[j-1] > target) {
        arr[j] = arr[j-1];
      } else {
        arr[j] = target;
        break;
      }
    }
  }
  
  return arr;
}

힐 정렬
힐 정렬 은 정렬 을 삽입 하 는 토대 에서 개 선 된 것 입 니 다. 매번 1 의 거리 가 아 닌 간격 을 설정 합 니 다. 간격 은 크 고 작은 것 이 며 마지막 은 1 입 니 다.
에서 Robert Sedgewick 은 동적 정의 간격 서열 을 제시 했다.(이해 하기 편 하도록 동적 정의 가 없습니다)

function shell(arr) {
  let gaps = [5, 3, 1];
  
  gaps.forEach((gap) => {
    for(let i = gap, len = arr.length; i < len; i++) {
      let target = arr[i];
      for(let j = i; j >=0; j -= gap) {
        if(arr[j - gap] > target) {
          arr[j] = arr[j - gap];
        } else {
          arr[j] = target;
          break;
        }
      }
    }
  });
  
  return arr;
}

빠 른 정렬
빠 른 정렬 은 하나의 기준 을 선택 한 다음 에 이 기준 보다 큰 것 을 한쪽 으로 하고 이 기준 보다 작은 것 을 다른 쪽 으로 한 다음 에 이 양쪽 을 같은 규칙 으로 처리 하 는 것 이다.이분법 과 유사 하 다.

function quick(arr) {
  if(arr <= 1) {
    return arr;
  }
  //      mid   arr      
  var mid = arr.shift();
  var left = [];
  var right = [];

  arr.forEach((value) => {
    if(value <= mid) {
      left.push(value);
    } else {
      right.push(value);
    }
  });

  return quick(left).concat(mid, quick(right));
}

정렬
이것 은 저도 설명 하기 어렵 습 니 다. 공식 적 인 표현 을 복사 하 겠 습 니 다.
병합 정렬 은 병합 작업 에 있어 효과 적 인 정렬 알고리즘 으로 이 알고리즘 은 분 치 법 (Divide and Conquer) 을 사용 하 는 매우 전형 적 인 응용 이다.기 존 서열 의 하위 서열 을 합쳐서 완전히 질서 있 는 서열 을 얻는다.즉, 모든 하위 서열 을 질서 있 게 한 다음 에 하위 서열 을 질서 있 게 하 는 것 이다.두 개의 질서 표를 하나의 질서 표 로 합치 면 2 번 병합 이 라 고 합 니 다.
다음은 제 가 찾 은 비교 이미지 의 병합 정렬 그림 입 니 다.
여 기 는 그림 데모 입 니 다.

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

function mergeSort(left, right) {
  var res = [];
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  
  while(left.length) {
    res.push(left.shift());
  }
  while(right.length) {
    res.push(right.shift());
  }
  
  return res;
}

각 정렬 알고리즘 의 복잡 도와 안정성 비교
알고리즘 종류
평균 시간 복잡 도
최 악의 시간 복잡 도
최 적 시간 복잡 도
공간 복잡 도
안정성
거품 정렬
O(n2)
O(n2)
O(n)
O(1)
안정시키다
정렬 선택
O(n2)
O(n2)
O(n2)
O(1)
불안정
삽입 정렬
O(n2)
O(n2)
O(n)
O(1)
안정시키다
힐 정렬
O(nlogn)
O(nlog2n)
O(nlog2n)
O(1)
불안정
빠 른 정렬
O(nlogn)
O(n2)
O(nlogn)
O(logn)
불안정
정렬
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
안정시키다
더미 정렬
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
불안정
(아직 정렬 을 이해 할 수 없습니다. 이 진 트 리 를 보고 정렬 을 연구 하면 정렬 된 내용 을 업데이트 할 수 있 습 니 다.)
각종 정렬 알고리즘 데모
여 기 를 누 르 면 각종 정렬 알고리즘 시연 을 볼 수 있 습 니 다.
총결산
전단 에서 이해 해 야 할 알고리즘 은 많 지 않 지만 알고리즘 을 최대한 많이 배 우 는 것 이 일부 코드 최적화 에 도움 이 되 고 나중에 다른 언어 를 배우 거나 깊이 공부 하 는 데 편리 합 니 다.