To sum up

1.binary search
2.selection sort
3. recursion
4.quicksort
5.hash tables
6.breadth first search
7,Dijkra's algorothm
8,greedy algorothm
9.dynamic programming
10.k nearest neighbors

list

array_list=[0]*6
print("最初的list是{}".format(array_list))
for i in range(6):
    array_list[i]=i
    print("第{}+1次的list是{}".format(i,array_list))

廣度優先搜尋(breadth first search)

節點(node)
邊(edge)
有向圖(directed graph)
無向圖(undirected graph)
佇列(queue)  FIFO(first in first out)
堆疊(stack)  FILO (first in last out)

快速排序法(quickSort)二

list 運用

list01=[88,5,3,77,33,22]

less=[i for i in list01 if i<=22]

larger=[j for j in list01 if j>22]

print(less)

print(larger)

==============
def qs(list):
   
    if (len(list)<2):
        return list
    else:
        pivot=list[0]
        less=[i for i in list[1:] if i<=pivot]
        larger=[i for i in list[1:] if i>pivot]
        return qs(less)+[pivot]+qs(larger)
list01=[12,42,245,24,88,77]
print(qs(list01))
    

快速排序法

quick sort
wiki
https://zhuanlan.zhihu.com/p/21839027

原地排序
   def quick_sort(alist, first, last):
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        while low < high and alist[high] >= mid_value:
            high= high - 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid_value:
            low =low + 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low-1)
    quick_sort(alist, low+1, last)

numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)

===============
def quick_sort(alist, first, last):
    print("alist是{},first是{},last是{}".format(alist,first,last))
    if first >= last:
        return
    mid_value = alist[first]
    print("mid_value是{}".format(mid_value))
    low = first
    print("low是{}".format(low))
    high = last
    print("high是{}".format(high))
    while low < high:
        while low < high and alist[high] >= mid_value:
            high =high-1
            print("high是{}".format(high))
        alist[low] = alist[high]
        print("alist[low]是{}".format(alist[high]))
        while low < high and alist[low] < mid_value:
            low =low+1
            print("low是{}".format(low))
        alist[high] = alist[low]
        print("alist[higt]是{}".format(alist[high]))
    alist[low] = mid_value
    quick_sort(alist, first, low-1)
    print("quick_sort(alist, first, low-1)是{}".format(alist))
    quick_sort(alist, low+1, last)
    print("quick_sort(alist, low+1, last)是{}".format(alist))
numbers = [9, 8, 7, 6, 99, 4, 3, 2, 56, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)



簡單版本




《Python cookbook 第二版》 from 知乎

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

一行語法

qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

list 相關函數

list01=[3,5,33,55,8,12]
print(list01)
list01.append(list01.pop(2))  #即list01增加為 list01移除的第二索引值
print (list01)

執行後為

[3, 5, 33, 55, 8, 12]   
[3, 5, 55, 8, 12, 33]

===============

list01=[3,5,33,55,8,12]
list02=["蘋果","香蕉","柳丁","葡萄","鳳梨"]
print(list01)
print(list02)
list01.append(list02.pop(2))
print (list01)
print(list02)

執行後為

[3, 5, 33, 55, 8, 12]
['蘋果', '香蕉', '柳丁', '葡萄', '鳳梨']
[3, 5, 33, 55, 8, 12, '柳丁']
['蘋果', '香蕉', '葡萄', '鳳梨']

遞迴演算法

遞迴演算法
定義：演算法(函式)中有呼叫自己(Self Calling)的敘述

from http://notepad.yehyeh.net/Content/DS/CH02/1.php
from https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-11ed5d300d3d
===========

def factorial(n):
    if n==0 or n==1:
        return 1
    else:
        return n*factorial(n-1)
print(factorial(5))

===========
def f(n):
    if (n==1):
        re=1
    else:
        re=n*f(n-1)
    print(n,"階乘等於",re)
    return re
n=int(input("enter number?"))
result=f(n)
print(n,"階乘等於",result)

==============from  https://sites.google.com/site/zsgititit/home/python-cheng-shi-she-ji/di-hui-python

選擇排序

找最小的數字
def findsmall(arr):
    smallest=arr[0]
    samllest_index=0
    for i in range(1,len(arr)):
        if (arr[i]<smallest):
            smallest=arr[i]
            smallest_index=i
    return smallest
list01=[13,5,6,7,82,22]
print(findsmall(list01))
========================================

def findmin(arr):
    min=arr[0]
    min_index=0
    for i in range(1,len(arr)):
        if (arr[i]<min):
            min=arr[i]
            min_index=i
    return min_index
#list01=[21,33,44,22,11,55]

def selecq(arr):
    newarr=[]
    for i in range(len(arr)):
        smallest=findmin(arr)
        newarr.append(arr.pop(smallest))
    return newarr
list01=[21,33,44,22,11,55]
print(selecq(list01))

=============其實有函數可以直接執行
list03=[33,22,55,11,88]
newlist05=sorted(list03)
print(list03)                      #原list 不變
print(newlist05)

    ==========或者是

list03=[33,22,55,11,88]
list03.sort()
newlist05=list03.sort()      #newlist05 變成 none
print(list03)
print(newlist05)

二進位搜尋法

適用於完成排序的清單

def binary_search(list,item):
    low=0
    high=len(list)-1
    while low<=high:
        mid=round((low+high)/2)
        guess=list[mid]
        if guess==item:
            return mid
        if guess>item:
            high=mid
        else:
            low=mid
    return None
my_list=[1,3,5,7,9,11]
print(binary_search(my_list,5))

====上述的程式 可能有誤

https://hugheschung.blogspot.com/2019/01/python3.html