アルゴリズムを理解する前に、アルゴリズムとは何かを見てみましょう。
定義：アルゴリズム（アルゴリズム）は、問題解決スキームの正確で完全な説明を指します。これは、問題を解決するための一連の明確な指示です。アルゴリズムは、問題を解決するための戦略メカニズムを説明する体系的な方法を表します。言い換えれば、特定の標準入力に対して限られた時間内に必要な出力を取得することが可能です。アルゴリズムに欠陥があるか、特定の問題に適していない場合、このアルゴリズムを実行しても問題は解決しません。アルゴリズムが異なれば、同じタスクを実行するために異なる時間、スペース、または効率を使用する場合があります。アルゴリズムの長所と短所は、空間の複雑さと時間の複雑さによって測定できます。
**python **の一般的なアルゴリズム
バブルソート
効率：O（n2）
原理：
隣接する要素を比較します。最初の要素が2番目の要素より大きい場合は、2つ交換します。
最初の最初のペアから最後の最後のペアまで、隣接する要素の各ペアに対して同じことを行います。終了後、最後の要素が最大数になります。ここでは旅行として理解できます。
最後の要素を除くすべての要素に対して上記の手順を繰り返します。
比較する数値のペアがなくなり、最後の数値シーケンスが最大から最小に配置されるまで、毎回、要素の数を減らして上記の手順を繰り返します。
def bubble_sort(data):"""
バブルソート
: param data::return:"""
for i inrange(len(data)-1): #旅行の数
for j inrange(len(data)-i-1): #データをトラバースし、順番に交換します
if data[j] data[j+1]: #大きい方が先に来るとき
data[j],data[j+1]=data[j+1],data[j] #2つの数字の位置を入れ替えます
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list)print("pre:",data_list)bubble_sort(data_list)print("after:",data_list)
# 結果：
# pre:[22,11,19,16,12,18,20,28,27,4,21,10,9,7,1,6,5,29,8,0,17,26,13,14,15,24,25,23,3,2]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
並べ替えを選択
効率：O（n2）
原理：
ソートするリストから要素を選択するたびに、他の番号と順番に比較されます。リスト内の番号が選択した番号よりも小さい場合は、位置が交換されます。すべての番号が比較された後、最小のものが選択されます。左端に配置します（このプロセスはトリップと呼ばれます）。
並べ替えるすべてのデータ要素が配置されるまで、上記の手順を繰り返します。
demo：
def select_sort(data):"""
並べ替えを選択
: param data:ソートするデータのリスト
: return:"""
for i inrange(len(data)-1): #旅行の数
min_index=i #iの先頭から最小数のインデックスを記録し、左端から開始します
for j inrange(i+1,len(data)): #各パスに必要なサイクル数
if data[j]< data[min_index]: #シーケンス内の数値が開始数値よりも小さい場合は、最小インデックス位置を更新します
min_index=j
data[i],data[min_index]=data[min_index],data[i] #1回のトリップの後、最小値の位置を入れ替えます。最初のトリップが最小になります
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list) #リストデータをシャッフルする
print("pre:",data_list)select_sort(data_list)print("after:",data_list)
# 結果：
# pre:[20,11,22,0,18,21,14,19,7,23,27,29,24,4,17,15,5,10,26,13,25,1,8,16,3,9,2,28,12,6]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
挿入ソート
効率：O（n2）
原理：
例として、小さいものから大きいものへの並べ替えを取り上げます。要素0が最初の要素です。挿入の並べ替えは、要素1から始まり、可能な限り前面に挿入されます。
挿入時は挿入位置と試行位置が分かれており、要素iの初期挿入位置はi、試行位置はi-1です。要素iを挿入する場合はi-1、i-2と比較します。仮位置の要素が挿入要素よりも大きい場合、仮要素が挿入要素よりも小さくなるか、挿入要素が最初の位置になるまで、仮要素が1位置後方に移動し、要素iの挿入位置が1位置前方に移動します。
上記の手順を繰り返し、最後に並べ替えを完了します
demo：
def insert_sort(data):"""
挿入ソート
: param data:ソートするデータのリスト
: return:"""
for i inrange(1,len(data)): #順序付けられていないエリアデータ
tmp = data[i] #i時間に挿入されたベンチマークの数
for j inrange(i,-1,-1):if tmp < data[j -1]: #jは現在の位置、テストj-1ポジション
data[j]= data[j -1] #現在地を移動
else: #場所はjとして決定されます
break
data[j]= tmp #現在の位置に戻す
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list) #リストデータをシャッフルする
print("pre:",data_list)insert_sort(data_list)print("after:",data_list)
# 結果：
# pre:[7,17,10,16,23,24,13,11,2,5,15,29,27,18,4,19,1,9,3,21,0,14,12,25,22,28,20,6,26,8]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
ヒープソート
ヒープの定義：基本的に完全なバイナリツリーです。ルートノードの値がすべてのノードの最小値である場合はスモールルートヒープと呼ばれ、ルートノードの値がすべてのノードの最大値である場合はビッグルートヒープと呼ばれます。
効率：O（nlogn）
原理：
ヒープ構造にソートするデータのリストを作成します（ヒープを作成します）。
shift_upやshift_downなどの操作では、パイルの一番上の要素が最大の要素になります（たとえば、パイルのルートが大きい）。
パイルの一番上の要素を削除し、最後の要素をパイルの一番上に置き、パイルを再調整して、パイルの一番上の要素を再び最大の要素にします（最初の要素と比較して2番目に大きい要素）。
ヒープが空になるまで3つの操作を繰り返し、最後に並べ替えを終了します。
マージソート
効率：O（nlogn）
スペースの複雑さ：O（n）
原理：
サイズが2つのソートされたシーケンスの合計になるようにスペースを申請します。このスペースは、マージされたシーケンスを格納するために使用されます。
2つのポインターを設定します。初期位置は、ソートされた2つのシーケンスの開始位置です。
2つのポインターが指す要素を比較し、マージスペースに配置する比較的小さな要素を選択して、ポインターを次の位置に移動します。
ポインタがシーケンスの最後に到達するまで、手順3を繰り返します。
別のシーケンスの残りのすべての要素を、マージされたシーケンスの最後に直接コピーします。
これまでのところ、Python言語のアルゴリズムはありますかに関するこの記事を紹介します。関連コンテンツについては、Pythonのアルゴリズムはありますか？ZaLou.Cnの以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後、ZaLouをさらにサポートしていただければ幸いです。 Cn！
Recommended Posts