アルゴリズムの基本概念と常用アルゴリズムPython実現

基本アルゴリズムの概念:
時間の複雑さ
時間の複雑さはその成長率の観点から測定され、
時間的複雑度は一般に大きなO法で表される.
 
再帰
再帰とは、自分の関数を呼び出すことです.
ループを使用すると、プログラムのパフォーマンスが向上する可能性があります.
再帰を使用すると、プログラムがより理解しやすいかもしれません.
ベースライン条件:関数は独自の条件を呼び出さなくなり、
再帰条件:関数は独自の条件を呼び出します.
 
二分法検索(再帰)(時間複雑度O(logn)):

def binary_search(arr, key):
    left = 0
    right = len(arr) - 1
    while right >= left:
        mid = (left + right)/2
        if key > arr[mid]:
            left = mid + 1
        elif key < arr[mid]:
            right = mid - 1
        else:
            return mid
    return -1


a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print binary_search(a, 11)

 
選択ソート(時間複雑度O(n 2):

def findSmallest(arr):
    smallest = arr[0]                     #       
    smallest_index = 0                    #          
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):                   #        
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)      #               
        newArr.append(arr.pop(smallest))
    return newArr

print selectionSort([5, 3, 6, 2, 10])

 
クイックソート(再帰):

def quicksort(array):
    if len(array) < 2:
        return array      #     ：               
    else:
        pivot = array[0]  #     
        lesser = [i for i in array[1:] if i <= pivot]  #                 
        greater = [i for i in array[1:] if i > pivot]  #               
        return quicksort(lesser) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

 
クイックソート(再帰的でない):
 

# -*- coding:utf-8 -*-
from collections import deque

def quick_sort(arr):
    deq = deque([0, len(arr) - 1])
    while deq:
        low = deq.popleft()
        l = low
        high = deq.popleft()
        h = high
        pivot = arr[low]
        while high > low:
            while high > low and arr[high] > pivot:
                high = high - 1
            arr[high], arr[low] = arr[low], arr[high]
            while high > low and arr[low] < pivot:
                low = low + 1
            arr[high], arr[low] = arr[low], arr[high]
        arr[high] = pivot
        m = high
        if m != l:
            deq.append(l)
            deq.append(m - 1)
        if m != h:
            deq.append(m + 1)
            deq.append(h)
    return arr

print quick_sort([24, 2, 3, 23, 4, 7, 5])

 
 
泡のソート:

def bubblesort(array):
    for i in range(len(array)):
        for j in range(len(array)-1-i):
            if array[j] < array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]

p = [1, 7, 9, 2, 3, 4, 5, 5]
bubblesort(p)
print p

 
集計ソート:

def merge(arr1, arr2):
    arr = []
    while len(arr1) != 0 and len(arr2) != 0:
        if arr1[0] > arr2[0]:
            arr.append(arr1.pop(0))
        else:
            arr.append(arr2.pop(0))
    return arr + arr1 + arr2

def mergeSort(array):
    if len(array) < 2:
        return array
    mid = len(array) / 2
    left = mergeSort(array[:mid])
    right = mergeSort(array[mid:])
    return merge(left, right)

c = [2, 6, 4, 0, 8, 5, 3]
print mergeSort(c)

 
転載先:https://www.cnblogs.com/weswes/p/9875340.html