Python을 사용하여 기수 정렬 알고리즘을 구현하는 방법은 무엇입니까?

Python을 사용하여 기수 정렬 알고리즘을 구현하는 방법은 무엇입니까?

Radix 정렬은 자릿수에 따라 정렬하는 알고리즘으로, 각 자릿수에 따라 정렬할 요소를 비교하여 정렬합니다. 이 기사에서는 Python을 사용하여 기수 정렬 알고리즘을 구현하는 방법을 배우고 자세한 코드 예제를 제공합니다.

알고리즘 구현 단계는 다음과 같습니다.

1단계: 정렬할 숫자 중 최대값을 찾고, 최대값의 자릿수를 결정합니다.

2단계: 개수 정렬을 사용하여 최대값의 자릿수를 기준으로 각 자릿수를 정렬합니다.

3단계: 모든 숫자가 고려될 때까지 2단계를 반복합니다.

4단계: 정렬된 결과를 출력합니다.

다음은 기수 정렬 알고리즘의 Python 코드 예제입니다.

# 定义计数排序的方法
def countSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 统计每个桶中元素的个数
    for i in range(n):
        index = arr[i] // exp
        count[index%10] += 1

    # 更新每个桶的位置
    for i in range(1, 10):
        count[i] += count[i-1]

    # 构建排序后的数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index%10] - 1] = arr[i]
        count[index%10] -= 1
        i -= 1

    # 将排序后的数组更新给原数组
    for i in range(n):
        arr[i] = output[i]


# 定义基数排序的方法
def radixSort(arr):
    # 找到待排序数组的最大值
    maxval = max(arr)

    # 根据最大值的位数进行排序
    exp = 1
    while maxval // exp > 0:
        countSort(arr, exp)
        exp *= 10


# 主函数调用基数排序算法
if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    radixSort(arr)
    print("排序后的数组：", arr)

위 코드에서는 먼저 counting 정렬 메서드 countSort를 정의하고 counting sort를 사용하여 지정된 자릿수에 따라 정렬할 배열을 정렬합니다. . 그런 다음 기수 정렬 메서드인 radixSort를 정의합니다. radixSort 메서드에서 정렬할 배열의 최대값을 찾고, 최대값의 자릿수에 따라 정렬하고, countSort 메서드를 호출하여 각 자릿수를 정렬합니다.

main 함수에서는 정렬할 배열 arr을 정의하고 정렬을 위해 radixSort 메서드를 호출합니다. 마지막으로 정렬된 배열을 출력합니다.

요약:

이 문서에서는 Python을 사용하여 기수 정렬 알고리즘을 구현하는 방법을 소개하고 자세한 코드 예제를 제공합니다. 이 기사를 읽으면 기수 정렬 알고리즘의 구현에 대해 더 깊이 이해할 수 있기를 바랍니다.

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