Python에서 Hill 정렬 알고리즘을 작성하는 방법은 무엇입니까?

Python에서 Hill 정렬 알고리즘을 작성하는 방법은 무엇입니까?

Shell Sort는 특정 간격으로 요소를 비교하여 요소를 이동함으로써 이동 횟수를 줄이는 향상된 삽입 정렬 알고리즘입니다. 힐 정렬의 핵심 아이디어는 정렬할 요소들을 일정한 간격으로 그룹화한 후, 각 그룹별로 삽입 정렬을 수행하고, 간격을 1이 될 때까지 계속해서 줄여 최종적으로 완전한 삽입 정렬을 수행하는 것이다.

아래에서는 Hill 정렬 알고리즘을 Python으로 작성하는 방법을 자세히 소개합니다.

먼저 삽입 정렬을 구현하는 함수를 작성해야 합니다. 삽입 정렬의 핵심 아이디어는 이미 정렬된 이전 시퀀스에 현재 요소를 삽입하는 것입니다.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

다음으로 정렬할 목록을 매개변수로 받는 Hill 정렬 함수를 작성합니다.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔设置为列表长度的一半
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2  # 缩小间隔

마지막으로 Hill 정렬의 정확성을 확인하는 테스트 함수를 작성합니다.

def test_shell_sort():
    arr = [12, 34, 55, 23, 8, 17, 45, 91]
    shell_sort(arr)
    assert arr == [8, 12, 17, 23, 34, 45, 55, 91]
    print("希尔排序测试通过！")

if __name__ == "__main__":
    test_shell_sort()

테스트 기능을 실행한 후 오류가 보고되지 않고 "Hill sort test pass!"라는 메시지가 출력되면 Hill sort 구현이 올바른 것입니다.

Hill 정렬의 시간 복잡도는 선택한 간격 시퀀스와 관련이 있습니다. 최적의 간격 시퀀스는 아직 발견되지 않았습니다. 힐 정렬의 평균 시간 복잡도는 약 O(n^1.3)이고, 최악의 경우 시간 복잡도는 약 O(n^2)입니다.

힐 정렬은 삽입 정렬에 비해 처음에 삽입 정렬 요소를 부분적으로 정렬할 수 있어 후속 비교 및 ​​이동 작업이 줄어들고 정렬 효율성이 향상되는 효율적인 정렬 알고리즘입니다. 목록을 빠르게 정렬하려면 Hill 정렬 알고리즘을 사용해 보세요.

위 내용은 Python에서 Hill 정렬 알고리즘을 작성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!