Python 選択ソートの実装と最適化ガイド

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 を使用して、最大要素の位置を記録します。各パスで、2 つの位置が比較によって更新され、交換されます。リストの長さが奇数の場合、min_pos と max_pos の位置がたまたま開始位置と一致した場合、入れ替わった位置を確認して処理する必要があります。

上記は、Python の選択ソートの手順と最適化方法、および具体的なコード例です。選択の並べ替えは単純ですが、効率が低く、時間計算量は O(n^2) です。したがって、実際のアプリケーションでは、ソートの規模が大きい場合は、クイック ソートやマージ ソートなど、より効率的なソート アルゴリズムを使用することをお勧めします。

以上がPython 選択ソートの実装と最適化ガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。