Python 선택 정렬 구현 및 최적화 가이드

파이썬 선택 정렬의 단계와 최적화 방법

선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 기본 아이디어는 매번 정렬할 데이터 요소에서 가장 작은(또는 가장 큰) 요소를 선택하고 이를 시퀀스의 시작 부분에 저장한 다음 정렬되지 않은 나머지 요소에서 가장 작은(또는 가장 큰) 요소를 계속해서 찾는 것입니다. , 정렬된 순서의 끝에 배치됩니다. 정렬할 모든 데이터 요소가 정렬될 때까지 이 과정을 반복합니다.

선택 정렬 단계는 다음과 같이 요약할 수 있습니다.

1. 정렬할 순서를 탐색하고 현재 위치를 가장 작은 요소의 위치로 표시합니다.
2. 표시된 위치 뒤의 요소에서 현재 가장 작은 요소보다 작은 요소를 찾아 표시된 위치를 업데이트하세요.
3. 표시된 위치의 요소를 최소 요소 위치의 요소로 교환하세요.
4. 표시된 위치 뒤의 요소를 새 시작 위치로 사용하고 2단계와 3단계를 반복하세요.

선택 정렬의 최적화 방법은 다음과 같습니다.

1. 각 순회에서 최소 요소와 최대 요소를 동시에 찾아서 동시에 교환합니다. 이를 통해 교환 횟수를 줄이고 분류 효율성을 높일 수 있습니다.
2. 판정 추가. 순회 과정에서 교환이 발생하지 않는 경우, 즉 정렬이 완료된 경우 정렬 프로세스가 조기 종료됩니다.

다음은 Python에서의 선택 정렬 코드의 예입니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_pos = i
        max_pos = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_pos]:
                min_pos = j
            if arr[j] > arr[max_pos]:
                max_pos = j
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
        if max_pos == i:
            max_pos = min_pos
        if max_pos != n - 1 - i:
            arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i]
        if min_pos == n - 1 - i:
            min_pos = max_pos
        if min_pos != i:
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
    return arr

# 测试
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
sorted_arr = selection_sort(arr)
print("排序后:", sorted_arr)

위 코드에서 우리가 사용하는 변수 min_pos 记录最小元素的位置，使用变量 max_pos 记录最大元素的位置。在每次遍历中，通过比较更新这两个位置，然后进行交换。在列表长度为奇数时，如果 min_pos 和 max_pos의 위치가 시작 위치와 우연히 일치하는데, 스왑된 위치를 확인하고 처리해야 합니다.

위 내용은 Python 선택 정렬의 단계 및 최적화 방법과 구체적인 코드 예제입니다. 선택 정렬은 간단하지만 효율성이 낮고 O(n^2)의 시간 복잡도를 갖습니다. 따라서 실제 응용에서는 정렬 규모가 클 경우 퀵 정렬이나 병합 정렬 등 보다 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.

위 내용은 Python 선택 정렬 구현 및 최적화 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!