1,000個(gè)の名前がリストされている紙が手に入っていて、そのうちの1つを見つける必要があると想像してください。このリストはアルファベット順ではありません。とてもイライラするでしょうね。このリストを整理するのに長い時(shí)間がかかりますが、名前を見つけるのははるかに簡単になります。したがって、物事を並べ替えることは私たちの人間の自然な欲求であり、ソートされたリストを検索することは、明らかに秩序だったリストを検索するよりも明らかに労力を節(jié)約します。

コンピューターの世界では、検索のリストは非常に大きく、高速なコンピューターでさえ、パフォーマンスが影響を受ける可能性があります。この場合、適切なソートおよび検索アルゴリズムがこのような問題の解決策となります。ソートは、値のリストを順番に並べ替えるプロセスであり、検索はリスト內(nèi)の値の位置を見つけるプロセスです。

この問題の重要性を説明するために、アメリカの偉大なコンピューター科學(xué)者のドナルドクヌースが言ったことをお見せしましょう。

1960年代のコンピューターメーカーは、すべての顧客を考慮して、コンピューターランタイムの25％以上がソートに費(fèi)やされたと推定しました。実際、多くのインストールの場合、ソートタスクは計(jì)算時(shí)間の半分以上を占めています。これらの統(tǒng)計(jì)から、（i）並べ替えには多くの重要なアプリケーションがある、または（ii）そうすべきではない場合に多くの人々がソートするか、（iii）非効率的なソートアルゴリズムが広く使用されていると結(jié)論付けることができます。 - - 「コンピュータープログラミングの技術(shù)」ボリューム3：ソートと検索、3ページ

このチュートリアルでは、選択ソートアルゴリズムと線形検索アルゴリズムの実裝方法を示します。

しかし、始める前に、Pythonコードをソートして検索したい場合は、組み込みの方法を示します。

Pythonの組み込みのソートメソッドと機(jī)能

Pythonを使用して多くのソートアルゴリズムを作成できます。これは優(yōu)れた學(xué)習(xí)演習(xí)ですが、生産アプリケーションでは、Pythonに組み込みの保存機(jī)能と方法に固執(zhí)する必要があります。

Pythonには、リストを內(nèi)側(cè)に並べ替えるために使用できる

メソッドがあります。 Pythonの舞臺(tái)裏で使用されるソートアルゴリズムは、Timsortと呼ばれます。これは、多くの実際の生活で優(yōu)れたパフォーマンスを提供する挿入並べ替えとマージソートに基づいたハイブリッドソートアルゴリズムです。これらの2つの機(jī)能と方法の使用方法の例は次のとおりです。

上記のコードの狀況の一部に気付くかもしれません。

関數(shù)は、元のリストを変更せずに新しい並べ替えられたリストを返します。ただし、元のリストは同じままです。一方、list.sort()の

メソッドを呼び出すと、

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

を返します。

いくつかのパラメーターを渡して、ソート動(dòng)作を変更できます。たとえば、関數(shù)をパラメーターなしでアルファベット順に並べ替えるreverseパラメーターに関數(shù)を渡します。 2番目のケースでは、ソートされた単語の順序を逆にするためにsorted()を使用します。 reverse=True

並べ替えアルゴリズム

を選択します

並べ替えアルゴリズムは、最小値または最大値の継続的な選択に基づいています。昇順で並べ替えたいリストがあるとします（小さいから大規(guī)模）。最小の要素はリストの先頭にあり、最大の要素はリストの最後にあります。

元のリストが次のように見えるとします：

| 7 | 5 | 3.5 | 4 | 3.1 |

最初にしなければならないことは、リスト內(nèi)の

最小値、この場合はの値を見つけることです。 3.1

最小値が見つかった場合、リストの最初の要素と最小値を交換

。つまり、と交換します。このリストは次のようになります： 3.1 7

リスト內(nèi)の最初の要素の正しい位置を決定したので、リストの2番目の要素から上記の手順（最小値を見つけます）を繰り返します。リスト內(nèi)の最小値（2番目の要素から始まる）は| 3.1 | 5 | 3.5 | 4 | 7 |であることがわかります。したがって、

と交換します。リストは次のようになります

この時(shí)點(diǎn)で、最初の要素と2番目の要素が正しい位置にあることを確認(rèn)します。 3.5 3.5次に、リストの殘りの部分の最小値を確認(rèn)します。つまり、3番目の要素5から始めます。リストの殘りの殘りの値は

であり、これを

と交換します。したがって、リストは次のようになります | 3.1 | 3.5 | 5 | 4 | 7 |

したがって、

最初の3つの要素が正しい位置にあり、この方法でプロセスが継続されると判斷しました。

Pythonで選択並べ替えアルゴリズムを?qū)g裝する方法を見てみましょう（Isai Damierに基づく）：5 4 5上記のスクリプトの最後に次のステートメントを追加して、アルゴリズムをテストしましょう。

この場合、次の出力を取得する必要があります。 | 3.1 | 3.5 | 4 | 5 | 7 |

線形検索アルゴリズム

線形検索

アルゴリズムは、リスト內(nèi)の各アイテムが目的のアイテムが見つかるか、リストの最後に到達(dá)するまでチェックされる（最初のアイテムから開始）単純なアルゴリズムです。

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

線形検索アルゴリズムは、次のようにPythonで実裝されています（Python Schoolに基づく）：

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

コードをテストしましょう。上記のPythonスクリプトの最後に次のステートメントを入力してください。

入力するときは、単一??の引用符または二重引用符の間にあることを確認(rèn)してください（つまり

）。たとえば、[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]と入力する場合、次の出力を取得する必要があります。

そして、入力としてを入力すると、次の出力が得られます。

Oops, your item seems not to be in the bag

結(jié)論

私たちが見たように、Pythonは、ここでソートと検索のアルゴリズムを扱うように、アルゴリズムの概念を簡単にプログラムできるプログラミング言語として再び証明します。

他の種類のソートおよび検索アルゴリズムがあることに注意する必要があります。 Pythonを使用してこれらのアルゴリズムをより深く掘り下げたい場合は、無料のPythonオブジェクト指向のプログラミングテキストを參照できます。

以上がPythonでのソートと検索の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。