> 일반적인 문제 > 삽입 정렬이란 무엇입니까?

삽입 정렬이란 무엇입니까?

藏色散人
풀어 주다: 2020-06-30 09:28:57
원래의
2992명이 탐색했습니다.

삽입 정렬에는 단순 삽입 정렬과 힐 정렬의 두 가지 유형이 있습니다. 단순 삽입 정렬의 시간 복잡도는 [O(N2) 안정 정렬]이고, 힐 정렬의 시간 복잡도는 [증분 시퀀스 선택과 관련이 있습니다. 안정적인 정렬].

삽입 정렬이란 무엇입니까?

삽입 정렬

간단한 삽입 정렬

정렬할 시퀀스 집합을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 초기 상태에서 정렬된 시퀀스에는 첫 번째 요소인 요소만 포함됩니다. 정렬되지 않은 시퀀스에는 첫 번째 요소를 제외하고 N-1개의 요소가 있으며, 정렬되지 않은 시퀀스의 요소는 정렬된 시퀀스에 하나씩 삽입됩니다. 이런 식으로 N-1 삽입 후 정렬되지 않은 시퀀스의 요소 수가 0이 되면 정렬이 완료됩니다.

시간 복잡도: O(N2) 안정 정렬

힐 정렬

정렬할 요소 집합 일정한 간격으로 여러 개의 시퀀스로 나누어 각각 삽입 정렬을 수행합니다. 처음에 설정된 "간격"은 상대적으로 크며 "간격"이 1이 될 때까지 정렬의 각 라운드에서 간격이 점차 감소합니다. 즉, 마지막 단계는 간단한 삽입 정렬을 수행하는 것입니다

시간 복잡도: 관련 증분 순서 선택 불안정 정렬

위 내용은 삽입 정렬이란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿