Python で選択ソートアルゴリズムを学習して実装する

Python での選択ソートの原理と実装を理解する

Selection Sort は、シンプルで直感的なソート アルゴリズムです。その基本的な考え方は、配列を毎回走査し、選択することです。未ソート部分の最小 (または最大) 要素を選択し、その位置を未ソート部分の最初の要素と交換し、未ソート部分から最小 (または最大) 要素を選択し続けるという手順を、配列全体が完了するまで繰り返します。順序付けられました。選択ソートの時間計算量は 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 回反復することになります。各反復で最小の要素が正しい位置に配置されるため、最後の要素は必要ありません。もう一度並べ替えます。

次に、2 つのネストされた 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 中国語 Web サイトの他の関連記事を参照してください。