增能班-演算法

 

Insertion Sort
------------------------------------------

>>> lst=[5,2,4,6,1,3]

               0 1 2 3 4 5

>>> for i in range(1,len(lst)):

for j in range(i,-1,-1):

print(j,end='')

print()

10

210

3210

43210

543210

------------------------------------------

>>> lst=[5,2,4,6,1,3]

>>> for i in range(1,len(lst)):

print("第",i,"回合")

for j in range(i-1,-1,-1):

if lst[i]<lst[j]:

lst[i],lst[j]=lst[j],lst[i]

i=j

print(lst)

print()

第 1 回合

[2, 5, 4, 6, 1, 3]

第 2 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 3 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 4 回合

[2, 4, 5, 1, 6, 3]

[2, 4, 1, 5, 6, 3]

[2, 1, 4, 5, 6, 3]

[1, 2, 4, 5, 6, 3]

第 5 回合

[1, 2, 4, 5, 3, 6]

[1, 2, 4, 3, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

------------------------------------------

def insertionsort(A):

    ''' 

    for i in range(1,len(A)):

        print("i=",i)

        for j in range(i-1,-1,-1):

            print("j=",j,end=" ")

        print()

    '''

    

    for i in range(1,len(A)):

        key=A[i]

        print("key=",key)

        for j in range(i-1,-1,-1):

        #    print("A[",j,"]=",A[j])

            if A[j]>key:                          

                A[j],A[i]=A[i],A[j] #i 往前1,與下一個A[j]比

                i=i-1

                print(A)

 

        print()

                          

    return A

nums = [5, 2, 4, 6, 1, 3]

print("排序完成:",insertionsort(nums))

= RESTART: F:\python\00.py =======================

key= 2

[2, 5, 4, 6, 1, 3]

key= 4

[2, 4, 5, 6, 1, 3]

key= 6

key= 1

[2, 4, 5, 1, 6, 3]

[2, 4, 1, 5, 6, 3]

[2, 1, 4, 5, 6, 3]

[1, 2, 4, 5, 6, 3]

key= 3

[1, 2, 4, 5, 3, 6]

[1, 2, 4, 3, 5, 6]

[1, 2, 3, 4, 5, 6]

排序完成: [1, 2, 3, 4, 5, 6]

-----------------------------------------------------

-----------InsertionSort

lst=[5,2,4,6,1,3]

for i in range(1,len(lst)):

    print("第",i,"回合")

    for j in range(i-1,-1,-1):

    if lst[i]<lst[j]:

    lst[i],lst[j]=lst[j],lst[i]

    i=j

    print(lst)

    print()

=========

第 1 回合

[2, 5, 4, 6, 1, 3]

第 2 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 3 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 4 回合

[2, 4, 5, 1, 6, 3]

[2, 4, 1, 5, 6, 3]

[2, 1, 4, 5, 6, 3]

[1, 2, 4, 5, 6, 3]

第 5 回合

[1, 2, 4, 5, 3, 6]

[1, 2, 4, 3, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

-----------------------------------------------------

-----------mergesort

import math

def Merge(items,l,m,r):

    n1=m-l+1

    n2=r-m

    lstL=[];lstR=[]

    for i in range(0,n1):

        lstL.append(items[l+i])

    for j in range(0,n2):

        lstR.append(items[m+j+1])

    lstL.append(math.inf)

    lstR.append(math.inf)

    i=0;j=0

    for k in range(l,r+1):

        if lstL[i]<=lstR[j]:

            items[k]=lstL[i]

            i+=1

        else:

            items[k]=lstR[j]

            j+=1

def MergeSort(items,l,r):    

    if l<r:

        m=math.floor((l+r)/2)

        MergeSort(items,l,m)

        MergeSort(items,m+1,r)

        Merge(items,l,m,r)                  

items=[5,2,4,7,1,3,2,6]

MergeSort(items,0,len(items)-1)

print(items)

=========

[1, 2, 2, 3, 4, 5, 6, 7]

+++++++++++++++++++++++

import math

Recsiv=0

def divide(Lst,ptrL,ptrR,LorR):

    global Recsiv

    Recsiv+=1

    

    print("Recsiv=",Recsiv," ptrL=",ptrL," ptrR=",ptrR,LorR)

    if ptrL<ptrR:

        ptrM=math.floor((ptrL+ptrR)/2)

        print("ptrM=",ptrM)

        print("00L=",Lst[ptrL:ptrM+1])

        print("00R=",Lst[ptrM+1:ptrR+1])

        print()

        

        divide(Lst,ptrL,ptrM,"左divide...")

        divide(Lst,ptrM+1,ptrR,"右divide...")

        conquer_combine(Lst,ptrL,ptrM,ptrR)

    else:

        print("已不符遞迴條件...")

        print()

def conquer_combine(Lst,ptrL,ptrM,ptrR):

    print("Recsiv=",Recsiv,"進入conquer_combine...")

    

    L=[i for i in Lst[ptrL:ptrM+1]]

    L.append(math.inf)

    print("L=",L)

    R=[i for i in Lst[ptrM+1:ptrR+1]]

    R.append(math.inf)

    print("R=",R)

    i=0;j=0    

    for k in range(ptrL,ptrR+1):

        if L[i]<=R[j]:

            Lst[k]=L[i]

            i+=1

        else:

            Lst[k]=R[j]

            j+=1

    print("目前Lst=",Lst)

    print()

#data=[2,4,5,7,1,2,3,6]

data=[9,7,5,2]

divide(data,0,len(data)-1,"第一次未分左右")

print("最後結果=",data)

=========

Recsiv= 1  ptrL= 0  ptrR= 3 第一次未分左右

ptrM= 1

00L= [9, 7]

00R= [5, 2]

Recsiv= 2  ptrL= 0  ptrR= 1 左divide...

ptrM= 0

00L= [9]

00R= [7]

Recsiv= 3  ptrL= 0  ptrR= 0 左divide...

已不符遞迴條件...

Recsiv= 4  ptrL= 1  ptrR= 1 右divide...

已不符遞迴條件...

Recsiv= 4 進入conquer_combine...

L= [9, inf]

R= [7, inf]

目前Lst= [7, 9, 5, 2]

Recsiv= 5  ptrL= 2  ptrR= 3 右divide...

ptrM= 2

00L= [5]

00R= [2]

Recsiv= 6  ptrL= 2  ptrR= 2 左divide...

已不符遞迴條件...

Recsiv= 7  ptrL= 3  ptrR= 3 右divide...

已不符遞迴條件...

Recsiv= 7 進入conquer_combine...

L= [5, inf]

R= [2, inf]

目前Lst= [7, 9, 2, 5]

Recsiv= 7 進入conquer_combine...

L= [7, 9, inf]

R= [2, 5, inf]

目前Lst= [2, 5, 7, 9]

最後結果= [2, 5, 7, 9]

-----------------------------------------------------

-----------InsertionSort

lst=[5,2,4,6,1,3]

for i in range(1,len(lst)):

    print("第",i,"回合")

    for j in range(i-1,-1,-1):

    if lst[i]<lst[j]:

    lst[i],lst[j]=lst[j],lst[i]

    i=j

    print(lst)

    print()

=========

第 1 回合

[2, 5, 4, 6, 1, 3]

第 2 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 3 回合

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

[2, 4, 5, 6, 1, 3]

第 4 回合

[2, 4, 5, 1, 6, 3]

[2, 4, 1, 5, 6, 3]

[2, 1, 4, 5, 6, 3]

[1, 2, 4, 5, 6, 3]

第 5 回合

[1, 2, 4, 5, 3, 6]

[1, 2, 4, 3, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

-----------------------------------------------------

-----------mergesort

import math

def Merge(items,l,m,r):

    n1=m-l+1

    n2=r-m

    lstL=[];lstR=[]

    for i in range(0,n1):

        lstL.append(items[l+i])

    for j in range(0,n2):

        lstR.append(items[m+j+1])

    lstL.append(math.inf)

    lstR.append(math.inf)

    i=0;j=0

    for k in range(l,r+1):

        if lstL[i]<=lstR[j]:

            items[k]=lstL[i]

            i+=1

        else:

            items[k]=lstR[j]

            j+=1

def MergeSort(items,l,r):    

    if l<r:

        m=math.floor((l+r)/2)

        MergeSort(items,l,m)

        MergeSort(items,m+1,r)

        Merge(items,l,m,r)

        

            

items=[5,2,4,7,1,3,2,6]

MergeSort(items,0,len(items)-1)

print(items)

=========

[1, 2, 2, 3, 4, 5, 6, 7]

-----------------------------------------------------

-----------BinarySearch

def BinarySerach(Lst,Key):

    Left=0

    Right=len(Lst)-1

    while Left<=Right:

        Mid=(Left+Right)//2

        if Lst[Mid]==Key:

            return Mid

        elif Lst[Mid]<Key:

            

                Left=Mid+1

        else:

            Right=Mid-1

    

Data=[1,3,5,7,9]

Target=3

FinalResult=BinarySerach(Data,Target)

print("搜尋目標 ",Target," 索引值=",FinalResult)

=========

搜尋目標  3  索引值= 1

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========

-----------------------------------------------------

-----------

=========