Python を使用して基数ソート アルゴリズムを実装するにはどうすればよいですか?

Python を使用して基数ソート アルゴリズムを実装するにはどうすればよいですか?

基数ソートとは、桁数に応じてソートするアルゴリズムで、ソート対象の要素を各桁の数値で比較してソートします。この記事では、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)

上記のコードでは、まずカウント ソート メソッド countSort を定義し、カウント ソートを使用して以下に従って配列をソートします。指定した桁数でソートします。次に、基数ソートメソッド radixSort を定義します。radixSort メソッドでは、ソート対象の配列の最大値を求め、最大値の桁数に従ってソートし、countSort メソッドを呼び出して各桁をソートします。

main 関数では、並べ替える配列 arr を定義し、並べ替えのために radixSort メソッドを呼び出します。最後に、ソートされた配列を出力します。

概要:

この記事では、Python を使用して基数並べ替えアルゴリズムを実装する方法を紹介し、詳細なコード例を示します。この記事を読んで、基数ソート アルゴリズムの実装についての理解を深めていただければ幸いです。

以上がPython を使用して基数ソート アルゴリズムを実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。