ソートの挿入(python)

4043 ワード
並べ替えの挿入 アルゴリズム
3.ソートの挿入(単純ソートの挿入)
3.1アルゴリズム思想
順序付けされたデータ・シーケンスがある場合、この順序付けされたデータ・シーケンスに数を挿入する必要がありますが、挿入後もこのデータ・シーケンスは順序付けされている必要があります.この場合、順序付け法を挿入する新しい順序付け方法が使用されます.順序付けを挿入する基本的な操作は、順序付けされた順序付けデータにデータを挿入し、新しい、長さが1増加した順序付けデータを得ることです.
ソートを挿入する基本的な考え方は、ステップごとにソートされるレコードをキー値の大きさで前にソートされたファイルの適切な位置に挿入し、すべて挿入が完了するまで挿入することです.
同様に,このアルゴリズムは余分な記憶空間を必要とせず,空間複雑度はo(1),時間複雑度はo(n^2)である.
3.2アルゴリズムプロセス
  • は、最初の要素から始まり、この要素は並べ替えられたと考えられる.
  • は、次の要素を取り出し、並べ替えられた要素シーケンスの中で後方から前方にスキャンする.
  • (ソートされた)要素が新しい要素より大きい場合、要素を次の位置に移動します.
  • は、並べ替えられた要素が新しい要素より小さいまたは等しい場所が見つかるまで、ステップ3を繰り返す.
  • 新しい要素をこの位置に挿入した後.
  • 手順2~5を繰り返します.順番が終わるまで.

    • 3.3 python実装
    def insertionSort(numList):
    n = len(numList)
    if n == 0 or n == 1:
        return numList
    for i in range(n):
        preIndex = i - 1
        current = numList[i]
        while preIndex >= 0 and current < numList[preIndex]:
            numList[preIndex+1] = numList[preIndex]
            preIndex -= 1
        numList[preIndex+1] = current
    return numList
numlist = [5,3,2,1,6,8,4,2,6]
print(insertionSort(numlist))
#      ：[1, 2, 2, 3, 4, 5, 6, 6, 8]
    PythonがJavaインタフェースを呼び出す——データ暗号化解読
    pythonソートアルゴリズムの実装コードの挿入