Shell Sort 소개 및 Python 구현
힐 정렬 은 체감 증분 정렬 알고리즘 이 라 고도 부 르 며 정렬 된 대학교 개선 버 전 을 삽입 하고 불안정 정렬 알고리즘 을 입력 합 니 다.힐 정렬 은 정렬 을 삽입 하 는 두 가지 특성 에 대해 개선 방법 을 제시 한 것 이다.
4. 567917. 정렬 을 삽입 하 는 것 은 이미 정렬 된 데이터 작업 효율 이 높 고 거의 선형 정렬 의 효율 에 달 합 니 다
4. 567917. 그러나 매번 데 이 터 를 한 명 만 이동 할 수 있 기 때문에 비효 율 적 이다
힐 정렬 의 시간 복잡 도 는 보폭 의 선택 과 관련 이 있 습 니 다. 최 악의 경우 시간 복잡 도 는 o (n log * 8289 ° 2 n) o (n\log ^ 2n) o (nlog2n) 로 가장 좋 은 비교 알고리즘 인 O (n log * 8289 ° n) O (n\log n) O (nlogn) 보다 조금 떨 어 집 니 다.보폭 서열 의 개선 은 시간 을 복잡 하 게 하 는 관건 이다. 이미 알 고 있 는 가장 좋 은 보상 서열 은 (1, 5, 19, 41, 109,..) (1, 5, 19, 41, 109,...) (1, 5, 19, 41, 109,...) (1, 5, 19, 41, 109, 109,..) 이다.이러한 서열 의 힐 정렬 은 작은 배열 의 정렬 에서 빠 른 정렬 과 쌓 기 정렬 보다 빠 르 지만 대량의 데 이 터 는 빠 른 정렬 보다 느리다.힐 정렬 은 비교 요 소 를 몇 개의 구역 으로 나 누 어 정렬 의 성능 을 향상 시 키 고 한 요 소 를 한꺼번에 최종 위치 로 크게 전진 시 킬 수 있 습 니 다. 그 다음 에 알고리즘 은 점점 작은 걸음 으로 정렬 할 수 있 습 니 다. 알고리즘 의 마지막 은 걸음 길이 가 1 일 때 간단 한 삽입 정렬 입 니 다. 이때 정렬 해 야 할 데 이 터 는 기본적으로 배열 되 어 있 습 니 다.힐 이 정렬 한 Python 은 다음 과 같 습 니 다. 코드 도 위 키 백과 에서 왔 습 니 다.
def ShellSort(array):
n = len(array)
gap = n//2
while gap>0:
for i in range(gap,n): # gap n
key = array[i]
while i>gap and array[i-gap]>key:
array[i] = array[i-gap]
i -= gap
array[i] = key
gap //= 2
return array
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준] 2170번: 선 긋기입력 x에 대해 오름차순으로 정렬합니다. 시작 정보(0번째 인덱스)를 저장하고, 1부터 (n-1)번째까지 순회합니다. 분리된 선인지 더 긴 선 정보가 있는지 확인하면서 길이를 누적해주고 길이 정보를 변경시켜줍니다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
