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

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

삽입 정렬

간단한 삽입 정렬

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

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

힐 정렬

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

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

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