python 資料結構

 

Bubble Sort
---------------------------------------------

>>> Lst=[3,7,1,6,2]

>>> for i in range(len(Lst),1,-1):

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

for j in range(i-1):

if Lst[j]>Lst[j+1]:

Lst[j],Lst[j+1]=Lst[j+1],Lst[j]

print(Lst)

print()

第 1 回合

[3, 7, 1, 6, 2]

[3, 1, 7, 6, 2]

[3, 1, 6, 7, 2]

[3, 1, 6, 2, 7]

第 2 回合

[1, 3, 6, 2, 7]

[1, 3, 6, 2, 7]

[1, 3, 2, 6, 7]

第 3 回合

[1, 3, 2, 6, 7]

[1, 2, 3, 6, 7]

第 4 回合

[1, 2, 3, 6, 7]

**5個元素,比較4回合,共比較(5*4)/2=10次

Bubble Sort

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

def BubbleSort(Lst):

    print("原始資料=",Lst)

    n=len(Lst)

    for i in range(0,n-1):

        print("\n第",i+1,"回合")

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

            if Lst[j-1]>Lst[j]:

                Lst[j-1],Lst[j]=Lst[j],Lst[j-1]

            print(Lst)

        print("比較：",n-i-1,"次")

    return Lst           

Data=[9,8,6,4,3]

Res=BubbleSort(Data)

print("\n最後結果：",Res)

=========

原始資料= [9, 8, 6, 4, 3]

第 1 回合

[8, 9, 6, 4, 3]

[8, 6, 9, 4, 3]

[8, 6, 4, 9, 3]

[8, 6, 4, 3, 9]

比較： 4 次

第 2 回合

[6, 8, 4, 3, 9]

[6, 4, 8, 3, 9]

[6, 4, 3, 8, 9]

比較： 3 次

第 3 回合

[4, 6, 3, 8, 9]

[4, 3, 6, 8, 9]

比較： 2 次

第 4 回合

[3, 4, 6, 8, 9]

比較： 1 次

最後結果： [3, 4, 6, 8, 9]

Selection Sort

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

>>> Lst=[3,6,1,7,2]

>>> for i in range(len(Lst)-1):

Min=i

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

for j in range(i+1,len(Lst)):

if Lst[Min]>Lst[j]:

Min=j

Lst[Min],Lst[i]=Lst[i],Lst[Min]

print(Lst)

print()

第 1 回合

[1, 6, 3, 7, 2]

第 2 回合

[1, 2, 3, 7, 6]

第 3 回合

[1, 2, 3, 7, 6]

第 4 回合

[1, 2, 3, 6, 7]

**5個元素,比較4回合,共比較(5*4)/2=10次

Selection Sort

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

def SelectionSort(Lst):

    print("OrignalData=",Lst)

    n=len(Lst)

    for i in range(0,n-1):

        print("\n第",i+1,"回合")

        Min=i

        for j in range(i,n):            

            if Lst[j]<Lst[Min]:

                Min=j

            #print("aa",Lst)

            

        print("TheMin=",Lst[Min])    

        Lst[i],Lst[Min]=Lst[Min],Lst[i]       

        

        print("目前 Lst=",Lst)

    return Lst

    

Data=[9,8,6,4,3]

Res=SelectionSort(Data)

print("\nFinalResult=",Res)

=========

OrignalData= [9, 8, 6, 4, 3]

第 1 回合

TheMin= 3

目前 Lst= [3, 8, 6, 4, 9]

第 2 回合

TheMin= 4

目前 Lst= [3, 4, 6, 8, 9]

第 3 回合

TheMin= 6

目前 Lst= [3, 4, 6, 8, 9]

第 4 回合

TheMin= 8

目前 Lst= [3, 4, 6, 8, 9]

FinalResult= [3, 4, 6, 8, 9]

Insertion Sort

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

def InsertionSort(Lst):

    print("OrignalData=",Lst)

    n=len(Lst)

    for i in range(1,n):

        print("\n第",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[j])

            print("目前排好：",Lst)

    return Lst

    

Data=[9,8,6,4,3]

Res=InsertionSort(Data)

print("\nFinalResult=",Res)

=========

OrignalData= [9, 8, 6, 4, 3]

第 1 回合

未排開始： 8

目前排好： [8, 9, 6, 4, 3]

第 2 回合

未排開始： 6

目前排好： [8, 6, 9, 4, 3]

未排開始： 6

目前排好： [6, 8, 9, 4, 3]

第 3 回合

未排開始： 4

目前排好： [6, 8, 4, 9, 3]

未排開始： 4

目前排好： [6, 4, 8, 9, 3]

未排開始： 4

目前排好： [4, 6, 8, 9, 3]

第 4 回合

未排開始： 3

目前排好： [4, 6, 8, 3, 9]

未排開始： 3

目前排好： [4, 6, 3, 8, 9]

未排開始： 3

目前排好： [4, 3, 6, 8, 9]

未排開始： 3

目前排好： [3, 4, 6, 8, 9]

FinalResult= [3, 4, 6, 8, 9]

Quick Sort

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

Heap Sort

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

Shell Sort

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

Merge Sort

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

Radix Sort

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

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

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