杭州Python学習進級のよくあるソートアルゴリズムの比較分析
4120 ワード
Pythonは人工知能時代の最良のプログラミング言語であり、科学演算、機械学習の主流言語でもある.高給のPythonエンジニアは、一般のPythonプログラマーに比べて、堅実な理論と豊富なプロジェクト経験だけでなく、アルゴリズムの把握も含まれています.次の杭州Python学習進級課程の編集者は、よくあるPythonソートアルゴリズムを共有します.
バブルソートBubbleSortバブルソートの原理は非常に簡単で、ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.具体的には、1)隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.2)0番目からn-1番目のデータについて同様の作業を行う.このとき,最大の数は配列の最後の位置に「浮かぶ」.3)最後の1つを除いて、すべての要素について上記の手順を繰り返します.4)比較する必要がなくなるまで、より少ない要素に対して上記の手順を繰り返します.参照コード:def bubble_sort 2(ary):n=len(ary)for i in range(n):flag=True#タグfor j in range(1,n-i):if ary[j]あるパスでデータ交換がなければ、説明は順序付けされているので、反復する必要はありません.
2、選択ソートSelectionSort選択ソートはもう一つの分かりやすく実現できる簡単なソートアルゴリズムである.具体的な手順:1)ソートされていないシーケンスで最小(大)要素を見つけ、ソートされたシーケンスの開始位置に格納します.2)残りのソートされていない要素から最小(大)要素を探し続け、ソートされたシーケンスの最後に配置します.3)すべての要素がソートされるまで、このようにします.参照コード:def select_sort(ary):n=len(ary)for i in range(0,n):min=i#最小要素下付きマーカーfor j in range(i+1,n):if ary[j]3、挿入ソートInsertionSort挿入ソートの動作原理は、ソートされていないデータごとに、ソートされたシーケンスの中で後ろから前へスキャンし、該当する位置を見つけて挿入することである.具体的な手順:1)最初の要素から開始します.この要素はすでにソートされていると考えられます.2)次の要素を取り出し、並べ替えられた要素のシーケンスで後から前へスキャンします.3)スキャンされた要素(ソートされた)が新しい要素より大きい場合は、その要素を1つ後ろに移動します.4)ソートされた要素が新しい要素より小さいまたは等しい場所が見つかるまで、手順3を繰り返します.5)新しい要素をその場所に挿入します.6)手順2-5を繰り返します.参照コード:
ソートの挿入
def insert_sort(ary):count=len(ary)for i in range(1,count):key=i-1 mark=ary[i]#注:ary[i]をmarkに割り当てる必要があり、ary[i]while key>=0 and ary[key]>mark:ary[key+1]=ary[key]=1 ary[key-=1 ary[key+1]=markreturnary
4、ヒルソートShellSortヒルソートの実質はパケット挿入ソートであり、この方法はインクリメンタルソートの縮小とも呼ばれる.参照コード:def shell_sort(ary):count = len(ary)gap = round(count/2)
平行棒は、pythonで直接「/」で得られる永遠の浮動小数点数を除去するために使用されます.
return ary
5、集計ソートMergeSort
集計ソートは、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは、2つ(または2つ以上)の順序付きテーブルを新しい順序付きテーブルに結合します.すなわち、順序付けされるシーケンスをいくつかのサブシーケンスに分割し、各サブシーケンスが順序付けされます.次に、順序付きサブシーケンスを全体の順序付きシーケンスに結合します.参照コード:
集計ソート
6、クイックソートQuickSortクイックソートは通常同じΟ(n log n)の他のアルゴリズムはもっと速いので、よく採用され、速い列は分治法の思想を採用しているので、多くの筆記試験の面接で速い列の影をよく見ることができます.速い列を身につけることの重要性がうかがえる.具体的な手順:1)数値列から基準数として1つの要素を選択します.
2)パーティション化プロセスは、ベースの準数より大きいものを右に、それ以下のものを左に配置します.3)さらに,各区間が1つになるまで,左右区間を再帰的に第2ステップを実行する.参照コード:def quick_sort(ary):returnqsort(ary,0,len(ary)−1)def qsort(ary,start,end): if start=key:right-=1 ifleft=keyary[right]=ary[left]right-=1 ary[left]=keyであることを示し、left=rightでピットを埋める
qsort(ary, left + 1, end)return ary
このほか,よく用いられるアルゴリズムにはスタックソート,基数ソートなども含まれており,ここではあまり説明しない.
バブルソートBubbleSortバブルソートの原理は非常に簡単で、ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.具体的には、1)隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.2)0番目からn-1番目のデータについて同様の作業を行う.このとき,最大の数は配列の最後の位置に「浮かぶ」.3)最後の1つを除いて、すべての要素について上記の手順を繰り返します.4)比較する必要がなくなるまで、より少ない要素に対して上記の手順を繰り返します.参照コード:def bubble_sort 2(ary):n=len(ary)for i in range(n):flag=True#タグfor j in range(1,n-i):if ary[j]
if flag:
break
return ary2、選択ソートSelectionSort選択ソートはもう一つの分かりやすく実現できる簡単なソートアルゴリズムである.具体的な手順:1)ソートされていないシーケンスで最小(大)要素を見つけ、ソートされたシーケンスの開始位置に格納します.2)残りのソートされていない要素から最小(大)要素を探し続け、ソートされたシーケンスの最後に配置します.3)すべての要素がソートされるまで、このようにします.参照コード:def select_sort(ary):n=len(ary)for i in range(0,n):min=i#最小要素下付きマーカーfor j in range(i+1,n):if ary[j]
ソートの挿入
def insert_sort(ary):count=len(ary)for i in range(1,count):key=i-1 mark=ary[i]#注:ary[i]をmarkに割り当てる必要があり、ary[i]while key>=0 and ary[key]>mark:ary[key+1]=ary[key]=1 ary[key-=1 ary[key+1]=markreturnary
4、ヒルソートShellSortヒルソートの実質はパケット挿入ソートであり、この方法はインクリメンタルソートの縮小とも呼ばれる.参照コード:def shell_sort(ary):count = len(ary)gap = round(count/2)
平行棒は、pythonで直接「/」で得られる永遠の浮動小数点数を除去するために使用されます.
# round()
while gap >= 1:
for i in range(gap, count):
temp = ary[i]
j = i
while j - gap >= 0 and ary[j - gap] > temp: #
ary[j] = ary[j - gap]
j -= gap
ary[j] = temp
gap = round(gap / 2)return ary
5、集計ソートMergeSort
集計ソートは、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは、2つ(または2つ以上)の順序付きテーブルを新しい順序付きテーブルに結合します.すなわち、順序付けされるシーケンスをいくつかのサブシーケンスに分割し、各サブシーケンスが順序付けされます.次に、順序付きサブシーケンスを全体の順序付きシーケンスに結合します.参照コード:
集計ソート
def merge_sort(ary):
if len(ary) <= 1:
return ary
median = int(len(ary)/2) #
left = merge_sort(ary[:median])
right = merge_sort(ary[median:])
return merge(left, right) #
def merge(left, right):
''' ，
left[] right[] '''
res = []
i = j = k = 0
while(i < len(left) and j < len(right)):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res = res + left[i:] + right[j:]
return res6、クイックソートQuickSortクイックソートは通常同じΟ(n log n)の他のアルゴリズムはもっと速いので、よく採用され、速い列は分治法の思想を採用しているので、多くの筆記試験の面接で速い列の影をよく見ることができます.速い列を身につけることの重要性がうかがえる.具体的な手順:1)数値列から基準数として1つの要素を選択します.
2)パーティション化プロセスは、ベースの準数より大きいものを右に、それ以下のものを左に配置します.3)さらに,各区間が1つになるまで,左右区間を再帰的に第2ステップを実行する.参照コード:def quick_sort(ary):returnqsort(ary,0,len(ary)−1)def qsort(ary,start,end): if start
qsort(ary, start, left - 1)qsort(ary, left + 1, end)return ary
このほか,よく用いられるアルゴリズムにはスタックソート,基数ソートなども含まれており,ここではあまり説明しない.