정렬 원리 와 구현 선택 (JS)

3869 단어 데이터 구조
정렬 선택
실현 원리
정렬 을 선택 하 는 것 은 원래 주소 비교 정렬 알고리즘 이다.대체적으로 데이터 구조 에서 가장 작은 값 을 찾 아 첫 번 째 에 두 고 두 번 째 작은 값 을 찾 아 두 번 째 에 두 는 것 으로 유추 된다.
구현 코드
function selectionSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  for (var i = 0; i < arr.length - 1; i++) {
    //    ,           ,      
    var minIndex = i;
    //              
    for (var j = i + 1; j < arr.length; j++) {
      //      arr[minIndex]             minIndex
      minIndex = arr[minIndex] > arr[j] ? j : i;
      //    ES6  
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

총결산
정렬 을 선택 하 는 데 있어 서 시간 복잡 도:
첫 번 째 내부 순환 비교 N - 1 번, 그 다음 N - 2 번, N - 3 번.
총 비교 횟수 는 (N - 1) + (N - 2) +... + 1, 등차 수열 과 득 (N - 1 + 1) * (N - 1) / 2 = N ^ 2 - N / 2 입 니 다.최고 항 계 수 를 버 리 고 시간 복잡 도 는 O (N ^ 2) 입 니 다.
정렬 알고리즘 이 불안정 하면 원본 시퀀스 를 파괴 할 수 있 습 니 다.

좋은 웹페이지 즐겨찾기