python 학습 노트 의 힐 정렬

힐 정렬
힐 정렬 (Shell Sort) 은 정렬 을 삽입 하 는 일종 이다.증분 정렬 을 축소 하 는 것 은 정렬 알고리즘 을 직접 삽입 하 는 더욱 효율 적 인 개선 버 전 이 라 고도 한다.힐 정렬 은 불안정 정렬 알고리즘 입 니 다.이 방법 은 DL. Shell 이 1959 년 제안 한 것 으로 이름 을 얻 었 다.힐 정렬 은 기록 을 아래 표 시 된 일정한 증분 으로 나 누 어 각 그룹 에 정렬 알고리즘 을 직접 삽입 하여 정렬 하 는 것 입 니 다.증분 이 점점 줄 어 들 면서 각 그룹 에 포 함 된 키워드 가 점점 많아 지고 증분 이 1 로 줄 어 들 면 전체 파일 이 한 그룹 으로 나 뉘 어 알고리즘 이 종 료 됩 니 다.
코드 는 다음 과 같다.

def shell_sort(li):
    n = len(li)
    gap = n//2

    while gap > 0:
        for i in range(gap,n):
            while i > gap and li[i-gap] > li[i]:
                li[i-gap],li[i] = li[i],li[i-gap]
                i -= gap
        gap = gap // 2

if __name__ == '__main__':
    li = [31, 42, 24, 56, 75, 51, 22, 65, 47, 87]
    shell_sort(li)
    print(li)