기본 알고리즘 (3) - 이분 정렬 (Java)

현재 주류 의 2 분 정렬 은 반절 삽입 정렬 이다.
정렬 을 한 번 에 직접 삽입 할 때 r [i]. key 에 게 앞의 i - 1 기록 은 키워드 에 따라 질서 가 있 습 니 다.이 때 정렬 방법 을 직접 삽입 하지 않 고 2 분 반 으로 바 꾸 어 r [i]. key 가 꽂 아야 할 위 치 를 찾 아 삽입 합 니 다.이런 방법 은 바로 반 으로 접 고 정렬 (2 분 정렬) 을 삽입 하 는 것 이다.
2 분 정렬 에서 키워드 의 비교 횟수 는 반절 검색 을 사용 하여 감소 하고 수량 급 은 o (nlogn) 이지 만 요소 이동 횟수 는 o (n ^ 2) 이 므 로 2 분 정렬 시간 복잡 도 는 o (n ^ 2) 이 고 2 분 정렬 은 안정 적 입 니 다.
      

좋은 웹페이지 즐겨찾기