Pythonは7つの基本的なアルゴリズムの実例的なコードを実現します。

5898 ワード

1.逐次検索
リストのようなセットにデータが格納されている場合、これらのデータは線形または順序関係を持っているという。各データ要素は、他のデータ要素に対する位置に格納されます。これらのインデックス値は秩序化されているので、順番にそれらにアクセスできます。このプロセス生産によって実現される検索は順序検索である。
順序検索の原理解析：リストの最初の要素から、基本的な順序で並べ替えて、簡単に要素から別の要素に移動します。完全なリストを巡回すると、検索中の要素が存在しないことを示します。
コード実装：関数は、リストと現在探している要素をパラメータとして必要とし、存在するかどうかのブール値を返します。foundブール変数はFalseに初期化されます。リストの要素を見つけたら、Trueに値が割り当てられます。


def search(alist,item):
 find = False
 cur = 0
 while cur < len(alist):
 if alist[cur] == item:
  find = True
  break
 else:
  cur += 1
 return find

2.二分検索
順序リストは我々の検索の実現に有用である。順序検索では、最初の要素と比較すると、最初の要素が私たちが検索したいものでない場合は、最大でn-1の要素と比較する必要があります。
二分割検索は、順番にリストを検索するのではなく、中間要素から始まります。この要素が私たちが探している要素であれば、検索を完了します。もしそれがないならば、リストの順序性を使って残りの要素の半分を除去することができます。
私たちが探している要素が中間要素より大きい場合、中間要素と中間要素より小さい半分の要素を除去できます。この要素がリストにあるなら、大きい部分に間違いない。そして、大きな半部分でこのプロセスを繰り返し、中間要素から始まり、私たちが探している内容と比較します。


def search(alist,item):
 left = 0
 right = len(alist) - 1
 find = False

 while left <= right:
 mid_index = (left + right)//2
 if item == alist[mid_index]:
  find = True
  break
 else:
  if item > alist[mid_index]:
  left = mid_index + 1
  else:
  right = mid_index -1

 return find

3.発泡体の並べ替え
原理:
隣接する要素を比較します。一番目が二番目より大きいなら、二人を交換します。各ペアの隣接元素に対して同じ仕事をして、最初のペアから最後のペアまでです。この点では、最後の要素は最大の数になるはずです。すべての要素に対して上記のステップを繰り返します。最後のステップを除いて。継続的に毎回、より少ない要素に対して上記のステップを繰り返し、数字のペアがないまで比較が必要です。


def sort(alist):
 length = len(alist)
 for i in range(0,length-1):
  for j in range(0,length-1-i):
  if alist[i] > alist[i+1]:
   alist[i],alist[i+1] = alist[i+1],alist[i]

4.並べ替えの選択
動作原理：最初に並べ替えられるデータ要素の中から最小（または最大）の要素を選択し、シーケンスの開始位置に保存し、残りの並べ替えられていない要素の中から最小（大）要素を探して、並べ替えられたシーケンスの最後に置く。この類推により、並べ替え対象のデータ要素の個数がゼロになるまで。ソートの選択は不安定なソート方法です。


def sort(alist):
 length = len(alist)
 for j in range(length-1,0,-1):
 max_index = 0
 for i in range(1,j+1):
  if alist[max_index] < alist[i]:
  max_index = i
 alist[max_index],alist[j] = alist[j],alist[max_index]

5.並べ替えの挿入
原理:
基本的な考え方は、各ステップにおいて順序付けされたレコードを、キーコード値の大きさによって前に並べられたファイルの中の適切な位置に挿入し、すべて挿入が終了するまで挿入することである。キーコードはデータ要素の中のデータ項目の値です。データ要素を表示してもいいです。


def sort(alist):
 length = len(alist)
 for j in range(1,length):
 i = j
 while i > 0:
  if alist[i] < alist[i-1]:
  alist[i],alist[i-1] = alist[i-1],alist[i]
  i -= 1
  else:
  break

ヒルの順序付け（Shell's Sort）は、挿入順序の一種であり、「縮小増分順序付け」（Diminishing Increment Sort）とも呼ばれ、直接並べ替えアルゴリズムを挿入するより効率的な改良バージョンである。ヒルの並べ替えは非定常的なソートアルゴリズムです。
この方法の基本的な考え方は、まず、配置される要素のシーケンス全体をいくつかのサブシーケンスに分割し（ある「インクリメント（gap）」からなる要素によって構成されている）、それぞれ直接挿入順序付けを行い、その後、順序を縮小して順序付けを行い、シーケンス全体の要素の基本的な順序（増分が十分小さい）になるまで、再度直接挿入順序付けを行うことである。直接挿入秩序化は元素の基本的秩序の場合（最高の場合に近い）に効率が高いので、直接挿入秩序に比べてヒル秩序化の時間効率が大幅に向上した。


def sort(alist):
 gap = len(alist)//2
 while gap >= 1:
 for j in range(gap,len(alist)):
  i = j
  while i > 0:
  if alist[i] < alist[i-gap]:
   alist[i],alist[i-gap] = alist[i-gap],alist[i]
   i -= gap
  else:
   break
 gap = gap // 2

6.快速並べ替え
基本的な考え方は、順序付けによって順序付けされるデータを独立した2つの部分に分割し、その一部のすべてのデータは他の部分のすべてのデータよりも小さい。そして、この方法によって、これらの2つの部分のデータをそれぞれ迅速に並べ替え、順序付けプロセス全体を再帰的に行うことができ、それによってデータ全体が秩序化される。


def sort(alist,start,end):
 low = start
 high = end
 if low >= high:
 return
 mid = alist[low]
 while low < high:
 while low < high:
  if alist[high] >= mid:
  high -= 1
  else:
  alist[low] = alist[high]
  break
 while low < high:
  if alist[low] < mid:
  low += 1
  else:
  alist[high] = alist[low]
  break
 alist[low] = mid
 sort(alist,start,low-1)
 sort(alist,high+1,end)

7.並べ替え
正規化順序付け（MERG-SORT）は、正規化動作において確立された効率的な順序付けアルゴリズムであり、このアルゴリズムは、ディヴィッド・アンド・Conquerを用いた非常に典型的な応用である。既存の順序のサブシーケンスを統合し、完全に秩序化されたシーケンスを得る。すなわち、各サブシーケンスを先に秩序化し、サブシーケンスセグメント間を秩序化させる。


def merge_sort(alist):
 n = len(alist)
 #       
 if n <= 1:
 return alist
 #    
 mid = n//2

 left_li = merge_sort(alist[:mid])
 right_li = merge_sort(alist[mid:])

 #              
 left_pointer,right_pointer = 0,0
 #         ：             
 result = []
 while left_pointer < len(left_li) and right_pointer < len(right_li):
 #          ，        result   
 if left_li[left_pointer] < right_li[right_pointer]:
  result.append(left_li[left_pointer])
  left_pointer += 1
 else:
  result.append(right_li[right_pointer])
  right_pointer += 1
 #                    ，      ，         （  ）   result 
 result += left_li[left_pointer:]
 result += right_li[right_pointer:]

 return result

alist = [3,8,5,7,6]
print(merge_sort(alist))

8.各アルゴリズムの時間複雑度

ここでPythonの7つの基本的なアルゴリズムを実現するための例示的なコードについての記事を紹介します。Pythonの基本的なアルゴリズムの内容については、以前の文章を検索したり、以下の関連記事を見たりしてください。これからもよろしくお願いします。

uuntu dockerについていくつかのこと（オススメ）

CentOS 7にNginx+MySQL教程をインストールします。