Python에서 선택 정렬 알고리즘을 배우고 구현합니다.

Python에서 선택 정렬의 원리와 구현을 이해하세요

선택 정렬은 매번 배열을 순회하여 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 선택하는 간단하고 직관적인 정렬 알고리즘입니다. , 정렬되지 않은 부분의 첫 번째 요소와 위치를 바꾼 다음 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 계속 선택하는 식으로 전체 배열이 정렬될 때까지 계속됩니다. 선택 정렬의 시간 복잡도는 O(n^2)이며 불안정한 정렬 알고리즘입니다.

다음은 특정 코드 예제를 사용하여 선택 정렬의 구현 프로세스를 보여줍니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

위는 선택 정렬 알고리즘의 구현 코드입니다. 다음으로 이 코드의 원리와 과정을 단계별로 설명하겠습니다.

먼저, 정렬할 배열 arr을 매개변수로 받는 Selection_sort 함수를 정의합니다.

함수 본문에서 먼저 배열의 길이 n을 얻습니다. 이는 n-1번 반복하는 것입니다. 각 반복이 가장 작은 요소를 올바른 위치에 배치하므로 마지막 요소를 정렬할 필요가 없기 때문입니다.

그런 다음 두 개의 중첩 for 루프를 사용하여 선택 정렬 프로세스를 수행합니다. 외부 루프는 0부터 n-1까지 진행되며, 이는 정렬할 부분의 시작 위치 i를 나타냅니다.

내부 루프는 i+1부터 n까지이며 정렬할 부분의 요소 j를 나타냅니다. j를 시작 위치 i의 요소와 비교합니다. j가 시작 위치 i의 요소보다 작으면 min_idx는 j로 업데이트되어 j가 지금까지 찾은 가장 작은 요소의 인덱스임을 나타냅니다.

내부 루프가 끝나면 발견된 가장 작은 요소의 위치를 ​​시작 위치 i의 요소와 교환하여 현재 반복에서 가장 작은 요소를 올바른 위치에 배치합니다.

n-1 반복을 통해 전체 배열이 오름차순으로 정렬되도록 할 수 있습니다.

다음으로 다음 코드를 사용하여 선택 정렬의 효과를 테스트할 수 있습니다.

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print(arr[i], end=" ")

출력 결과는 11 12 22 25 64이며 이는 배열이 오름차순으로 정렬되었음을 의미합니다.

실제 사용에서는 선택 정렬의 효율성이 떨어지기 때문에 퀵 정렬이나 병합 정렬 등 좀 더 효율적인 다른 정렬 알고리즘을 사용하는 것을 선호합니다. 그러나 선택 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘으로, 초보자가 정렬 알고리즘의 기본 원리와 아이디어를 이해하는 데 도움이 됩니다.

정리하자면, 선택 정렬은 매번 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 선택하여 정렬된 부분의 끝에 놓고 여러 번의 반복을 거쳐 최종적으로 전체 배열을 정렬하는 목적을 달성하는 것입니다. 선택 정렬의 원리와 구현을 익히는 것은 정렬 알고리즘을 심층적으로 이해하고 프로그래밍 능력을 향상시키는 데 큰 의미가 있습니다.

위 내용은 Python에서 선택 정렬 알고리즘을 배우고 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!