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

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

삽입 정렬은 정렬할 배열을 순서가 있는 부분과 순서가 없는 부분으로 나눌 때마다 순서가 없는 부분에서 요소를 선택하여 올바른 위치에 삽입하는 것입니다. 주문한 부분 . 삽입 정렬 알고리즘의 구현은 일반적으로 O(n^2)의 시간 복잡도로 요소를 여러 번 비교하고 교환하여 구현됩니다.

파이썬에서 삽입 정렬 알고리즘을 작성하는 방법과 구체적인 코드 예제를 살펴보겠습니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

위는 삽입 정렬 알고리즘의 구체적인 구현 코드입니다. 메인 함수에서는 정렬할 배열 arr을 전달하고 정렬된 결과를 반환해야 합니다.

알고리즘의 메인 루프에서는 두 번째 요소부터 시작하여 이를 삽입할 요소의 키로 사용합니다. 그런 다음 키를 정렬된 부분의 마지막 요소와 비교하여 키의 올바른 위치를 찾을 때까지 키보다 큰 요소를 뒤로 이동합니다. 마지막으로 키를 올바른 위치에 삽입합니다.

다음으로 삽입 정렬 알고리즘을 테스트할 수 있습니다.

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

출력 결과는 다음과 같습니다.

[1, 2, 5, 6, 8, 9]

삽입 정렬 알고리즘을 통해 입력 배열을 오름차순으로 성공적으로 정렬한 것을 확인할 수 있습니다.

요약하자면, 삽입 정렬 알고리즘을 Python으로 작성하는 것은 복잡하지 않습니다. 삽입정렬의 기본 개념을 이해하고, 그 아이디어를 바탕으로 해당 코드를 구현하면 됩니다. 물론 코드를 더욱 강력하고 다양하게 만들기 위해 빈 배열이나 요소가 하나만 있는 배열과 같은 극단적인 경우도 처리할 수 있습니다.

이 기사가 삽입 정렬 알고리즘을 이해하고 마스터하는 데 도움이 되기를 바랍니다!

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