python_demo

*バブルソートアルゴリズムは次のように動作します.
隣接する要素を比較します.1番目が2番目より大きい(昇順)場合は、2つを交換します.各ペアの隣接要素について同じ作業を行い、最初のペアから最後のペアまで行います.このステップが終わると、最後の要素が最大の数になります.最後の1つを除いて、すべての要素について上記の手順を繰り返します.数値のペアが比較されないまで、要素の数が少なくなるたびに上記の手順を繰り返します.*

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

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

選択ソート(Selection sort)は単純で直感的なソートアルゴリズムである.その動作原理は以下の通りです.まず、ソートされていないシーケンスで最小(大)要素を見つけ、ソートされたシーケンスの開始位置に保存し、残りのソートされていない要素から最小(大)要素を探し続け、ソートされたシーケンスの最後に配置します.すべての要素がソートされるまで、このようにします.

def selection_sort(alist):
    n = len(alist)
    #     n-1     
    for i in range(n-1):
        #       
        min_index = i
        #  i+1            
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        #               ，    
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

挿入ソート(英語:Insertion Sort)は、単純で直感的なソートアルゴリズムです.秩序化されたシーケンスを構築し、並べ替えられていないデータに対して、並べ替えられたシーケンスを後方から前方にスキャンし、対応する位置を見つけて挿入することが原理です.挿入ソートは実装上、後から前へスキャンする過程で、ソートされた要素を徐々に後ろに移動し、最新の要素に挿入空間を提供することを繰り返す必要があります.

def insert_sort(alist):
    #       ，    1         
    for i in range(1, len(alist)):
        #   i         ，         ，    
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)

*クイックソート(英語:Quicksort)は、分割交換ソート(partition-exchange sort)とも呼ばれ、1回のソートでソートするデータを独立した2つの部分に分割し、その一部のすべてのデータが他の部分のすべてのデータよりも小さくなり、この方法でこの2つの部分のデータをそれぞれクイックソートし、ソートプロセス全体を再帰的に行うことができます.これにより、データ全体が秩序化されたシーケンスになります.
手順は次のとおりです.
数列から1つの要素を選択して「基準」(pivot)と呼び、数列を並べ替え、すべての要素が基準値より小さいものを基準の前に配置し、すべての要素が基準値より大きいものを基準の後ろに配置する(同じ数はどちらにでもよい).このパーティションが終了すると、基準は数列の中間位置にあります.これをパーティション操作と呼ぶ.再帰的に(recursive)基準値要素より小さいサブ数列と基準値要素より大きいサブ数列を並べ替えます.*

def quick_sort(alist, start, end):
    """    """

    #        
    if start >= end:
        return

    #                  
    mid = alist[start]

    # low               
    low = start

    # high               
    high = end

    while low < high:
        #   low high   ，high            ， high    
        while low < high and alist[high] >= mid:
            high -= 1
        #  high       low    
        alist[low] = alist[high]

        #   low high   ，low           ， low    
        while low < high and alist[low] < mid:
            low += 1
        #  low       high    
        alist[high] = alist[low]

    #      ，low high  ，                
    #           
    alist[low] = mid

    #                  
    quick_sort(alist, start, low-1)

    #                  
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)

ヒルソート(Shell Sort)は、ソートを挿入するものです.インクリメンタルソートの縮小とも呼ばれ、ソートアルゴリズムを直接挿入するより効率的な改良バージョンです.ヒルソートは非安定ソートアルゴリズムである.この方法はDL.Shellが1959年に提案したことから名付けられた.ヒルソートは、レコードを下付きの一定の増分でグループ化し、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、ファイル全体がグループに分けられ、アルゴリズムは終了する.

def shell_sort(alist):
    n = len(alist)
    #     
    gap = n / 2
    while gap > 0:
        #          
        for i in range(gap, n):
            j = i
            #     
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        #       
        gap = gap / 2

alist = [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)

*集計ソートは、分治法を採用する非常に典型的な応用です.集計ソートの考え方は,まず配列を再帰的に分解し,配列を統合することである.
配列を最小に分解した後、2つの秩序配列をマージします.基本的な考え方は、2つの配列の一番前の数を比較し、小さい人はまず誰を取り、取った後、対応するポインタは1つ後ろに移動します.次に、ある配列が空になるまで比較し、最後に別の配列の残りの部分をコピーすればいいです.*

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    #     
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    #   
    return merge(left,right)

def merge(left, right):
    '''    ，       left[] right[]           '''
    #left right     
    l, r = 0, 0
    result = []
    while l

二分検索は折半検索とも呼ばれ、比較回数が少なく、検索速度が速く、平均性能が良いという利点がある.その欠点は,調査対象テーブルが整列テーブルであること,挿入削除が困難であることである.したがって,折半ルックアップ手法は,頻繁に変動せずに頻繁にルックアップするシーケンステーブルに適している.まず、表の要素が昇順に並べられていると仮定し、表の中間位置に記録されたキーワードを検索キーワードと比較し、両者が等しい場合、検索に成功する.そうでなければ、中間位置レコードを使用してテーブルを前後の2つのサブテーブルに分割し、中間位置レコードのキーワードが検索キーワードより大きい場合は、前のサブテーブルをさらに検索し、そうでなければ後のサブテーブルをさらに検索します.条件を満たすレコードが見つかり、検索が成功するまで、またはサブテーブルが存在しないまで、上記の手順を繰り返します.

（     ）
def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
（    ）
def binary_search(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
          return True
        else:
          if item