Pythonで挿入ソートアルゴリズムを記述するにはどうすればよいですか?

Python で挿入ソート アルゴリズムを記述するにはどうすればよいですか?

挿入ソートは、シンプルで直観的なソート アルゴリズムです。その考え方は、ソートされる配列を順序付き部分と順序なし部分に分割することです。毎回、順序なし部分から要素が選択され、配列に挿入されます。注文した部品の正しい位置。挿入ソート アルゴリズムの実装は通常、要素を複数回比較および交換することによって実装され、時間計算量は O(n^2) です。

Python 言語での挿入ソート アルゴリズムの記述方法と、具体的なコード例を見てみましょう。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]              # 当前待插入元素
        j = i - 1                 # 有序部分的最后一个元素索引

        # 将比key大的元素都向后移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key           # 将key插入正确位置

    return arr

上記は、挿入ソート アルゴリズムの具体的な実装コードです。 main 関数では、並べ替えられる配列 arr を渡し、並べ替えられた結果を返す必要があります。

アルゴリズムのメイン ループでは、2 番目の要素から開始し、それを挿入する要素のキーとして使用します。次に、キーとソートされた部分の最後の要素を比較し、キーの正しい位置が見つかるまで、キーより大きい要素を 1 つ後方に移動します。最後に、キーを正しい場所に挿入します。

次に、この挿入ソート アルゴリズムをテストします。

arr = [9, 5, 1, 6, 8, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

出力結果は次のとおりです:

[1, 2, 5, 6, 8, 9]

ご覧のとおり、挿入ソート アルゴリズムにより、入力配列を昇順に並べることができました。

要約すると、Python での挿入ソート アルゴリズムの作成は複雑ではありません。挿入ソートの基本的な考え方を理解し、その考え方に基づいて対応するコードを実装するだけです。もちろん、コードをより堅牢かつ多用途にするために、空の配列や要素が 1 つだけの配列などのエッジ ケースも処理できます。

この記事が、挿入ソート アルゴリズムを理解して習得するのに役立つことを願っています。

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