---
# System prepended metadata

title: 資訊選修-Python By Liao-Hsiu-I

---

---
title: '資訊選修-Python By Liao-Hsiu-I'
disqus: hackmd
---

資訊選修-Python By Liao-Hsiu-I
===

[TOC]

基礎程式設計-複習(高一)(9/3)(第一堂)
---
### 觀念驗證題
##### 題目1題目敘述:![](https://i.imgur.com/slB7RWc.png)
```python=
classnum=input("班級座號:")
name=input("班級座號:")
num=input("班級座號:")
print("您的資訊為"+classnum+name)
print("密碼設定為:"+num)
```
##### 題目2題目敘述:
每位同學輸入受測者的班級座號、身高、體重
利用多向條件判斷(要求如下)
BMI的標準18.5<=BMI<24
1.當BMI小於18.5，會送出[太瘦了];
2.當BMI太大時，則是送出[該減重了];
3.當BMI在標準值內，則列印出[標準!]。
```python=
classnum=input("班級座號:")
height=(float(input("請輸入身高")))/100
weight=float(input("請輸入體重"))
BMI=weight/(height*height)
if(BMI>24 or BMI==24):
  print("減重了")
elif(BMI<18.5):
  print("太瘦了")
else:
  print("標準")
```
### 延伸題
##### 題目3題目敘述:
讓使用者輸入一個正整數，然後判斷它是3或5的倍數。
若此數值同時為3與5的倍數→顯示[x為3與5的倍數]:
若此數值為3的倍數→顯示[x為3的倍數];
若此數值為5的倍數→顯示[x為5的倍數];
如此數值皆不屬於 3 或 5 的倍數→顯示[x不為3與5的倍數]。
```python=
num=int(input("請輸入數字"))
if(num%3==0):
  if(num%3==0):
    print("x 為 15 的倍數")
  else:
    print("x 為 3 的倍數")
elif(num%5==0 and num%3!=0):
  print("x 為 5 的倍數")
else:
  print("x 不為 3 與 5 的倍數")
```
##### 題目4題目敘述:
請輸入身份證字號進行男女性別與戶籍(北北基)的判斷設定條件:
1. 開頭英文大小寫都可以
2. 臺灣身分證字號長度須為 10
3. 若為男生,則印出”先生您好,您的戶籍地為......”
若為女生,則印出”小姐您好,您的戶籍地為......”

-提示:
A或Y台北市；F新北市；C基隆市；其他不是北北基。
```python=
identity=input("請輸入身分帳字號")
while True:
  if(len(identity)==10):
    break
  else:
    print("輸入錯誤")
    identity=input("請輸入身分帳字號")
Identity=identity.upper()
if(Identity[1]=="1"):
  if(Identity[0]=="A" or Identity[0]=="Y"):
    print(" 先生您好，您的戶籍地為台北市")
  elif(Identity[0]=="F"):
    print(" 先生您好，您的戶籍地為新北市")
  elif(Identity[0]=="C"):
    print(" 先生您好，您的戶籍地為基隆市")
elif(Identity[1]=="2"):
  if(Identity[0]=="A" or Identity[0]=="Y"):
    print(" 小姐您好，您的戶籍地為台北市")
  elif(Identity[0]=="F"):
    print(" 小姐您好，您的戶籍地為新北市")
  elif(Identity[0]=="C"):
    print(" 小姐您好，您的戶籍地為基隆市")
```
基礎程式設計(高一)(9/10)(第二堂)
---
### 觀念驗證題
##### 題目1題目敘述:
利用while與for迴圈分別撰寫程式，
列印15次自己的班級座號姓名(含目前列印至第幾次)。
```python=
#for迴圈
nameclass=input("請輸入班級座號")
for j in range(15):
  print("第"+str(j+1)+"次打印"+nameclass)
#while迴圈
nameclass=input("請輸入班級座號")
count=0
while(count<15):
    print("第"+str(count+1)+"次打印"+nameclass)
    #0-14共15次
    count+=1
```
##### 題目2題目敘述:
利用利用while與for迴圈分別撰寫程式
請輸入1個正整數n的值，則計算1+2+3+......+n
，並呈現在電腦螢幕上。
```python=
#解1
#for迴圈
total=1
number=int(input("請輸入數字"))
for i in range(number):
  total+=i
print(total)
#while迴圈
total=0
number=int(input("請輸入數字"))
i=0
while(i<=number):
  total+=i
  i+=1
print(total)
#解2
#等差級數總和可由等差總和公式n(n+1)/2求得(n為項數)
number=int(input("請輸入數字"))
print(n(n+1)/2)
```
##### 題目3題目敘述:
請撰寫一程式，讓程式不斷列印1~20間的亂數，但亂數遇到5的倍數不列印，遇到11會結束。
```python=
import random
while True: 
  num=random.randint(1,20)
  if(num%5!=0): #num!=0(mod 5)打印
    print(num)
  if(num==11):
    break
```
### 延伸題
##### 題目4題目敘述:
請撰寫一個程式，先亂數取1-100之間的1個
數字(包含1-100)當作密碼，讓使用者不斷的猜
測,直到猜到正確的答案為止。
使用者每猜一個數字，程式會把範圍縮小，界定
出最大與最小值的可猜範圍。
如果使用者猜的數字超出此範圍之外，則會顯示
超出範圍的訊息。

輸入輸出說明:
-遊戲流程:
假定系統亂數定出88為密碼。
-範例輸入:
請輸入1-100間的數字 : (使用者輸入50)
請輸入50-100間的數字 : (使用者輸入25)
猜測數值超過範圍，請輸入50-100間的數字 : (使用者輸入75)
請輸入76-100間的數字 : (使用者輸入90)
...
答對了，密碼為88。
```python=

import random
passcode=random.randint(1,100)
min=1
max=100
while True:
  guess=int(input("請輸入"+str(min)+"-"+str(max)+"間的數字 : "))
  if(passcode==guess):
    print("答對了，密碼為"+str(passcode))
    break
  elif(guess>passcode and min<=passcode=<max):
    max=guess-1
  elif(guess<passcode and min<=passcode=<max):
    min=guess+1
  else:
    print("猜測數值超過範圍，"+"請輸入"+str(min)+"-"+str(max)+"間的數字 : ")
```
##### 題目6題目敘述:
以知大樂透號碼由標準號6碼與特別號1碼所組成
請撰寫一程式，讓系統隨機從1~49 中，
開出6個號碼(標準號)、及1個特別號(號碼不可重複)。
-輸出範例:
樂透中獎號碼 : 2 5 25 26 37 42
特別號 : 8
```python=
import random
lotta=[]
for i in range(7):
  randi=random.randint(1,49)
  if randi not in lotta:
    lotta.append(randi)
    i-=1
print("樂透中獎號碼 :",end=" ")
for i in range(6):
  print(lotta[i],end=" ") 
  #print(lotta[頭:尾])亦可
print()
print("特別號 : "+str(lotta[6]))
```
基礎程式設計(9/17)(第三堂)
---
### NOTE
①格式
```python=
def 函數名稱 (參數):
    內容
函式名稱( ) #呼叫函式
```
②創造函式目的
1.增強程式架構性
2.重複使用時呼叫即可
e.g.:
```python=
def wash(dry): #def before calling
  print("加水")
  print("加洗衣精")
  print("旋轉")
  if(dry):
    print("烘衣")
wash(True)

```
有參數函數
①當function需要用到外部資料,就設計參數,把資料投進去function裡
②如果function有參數設定,就一定要投東西(除非有預設值)
參數可以不只一個 (多個參數 用 , 隔開)
③投東西的時候是按照參數的順序
④參數可以有”預設值”,就不一定要投東西給參數
⑤投東西給參數時,可以”明確指定”要投給哪一個參數

### 題目們
```python=
#0
def add(x,y):
  print(x+y)
add(2)#依序儲存x=2

```
```python=
#1
def power(x,y):
  return x**y
number1=int(input("請輸入底數數字"))
number2=int(input("請輸入次方數字"))
result=power(x=number1,y=number2)
print(number1,"的",number2,"次方為",result)
```

```python=
#2
def nroot(x,y):
  return x**(1/y)
number1=int(input("請輸入被開方數字"))
number2=int(input("請輸入開方數字"))
result=nroot(x=number1,y=number2)
print(number1,"開",number2,"次方為",result)
```
```python=
#3
def equation(a,b,c):
  D=b**2-4*a*c
  if(D<0):
    return("無解")
  if (D==0):
    return str((-b/(2*a)))
  if (D>0):
    m=(-b+(D)**(1/2))/(2*a)
    n=((-b-(D)**(1/2))/(2*a))
    return str(m)+","+str(n)
number1=int(input("請輸入方程式係數a:"))
number2=int(input("請輸入方程式係數b:"))
number3=int(input("請輸入方程式係數c:"))
p=equation(number1,number2,number3)
print("方程式的解為",p)
```

```python=
#4
shopping_list=[]#[goods][price]
while True:
  goods_name=input("請輸入商品名稱")
  goods_price=input("請輸入商品名稱")
  if(goods_name=="q"):
    break
  data=[goods_name, goods_price]
  shopping_list.append(data)
  

```
基礎程式設計(9/24)(第四堂)
---
### 觀念驗證題
### 延伸題
基礎程式設計(10/8)(第五堂)
---
### 記帳程式
##### 題目6題目敘述:
```python=
products=[]
while True:
  name=input("請輸入商品名稱")
  if  name=="q":
    break
  price=int(input("請輸入商品價格:"))
  p = [ ]
  p.append(name)
  p.append(price)
  products.append(p)
             
print(products)
for p in products:
  print(p[0],"價格是",p[1])

with open("products.csv","w") as f:
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
  f.write("名稱"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
  for p in products:
    f.write(p[0]+","+str(p[1])+"\n")
```
基礎程式設計(10/15)(第六堂)
---
### 記帳程式(有檔案之情況)
```python=
products=[]
with open("products.csv","r",encoding="utf-8") as f: #"r"=read
  for line in f:
    if "商品,價格" in line:
      continue
    name, price=line.strip().split(",")
    print([name,price])
    products.append([name,price])
    
while True:
  name=input("請輸入商品名稱")
  if  name=="q":
    break
  price=int(input("請輸入商品價格:"))
  p = [ ]
  p.append(name)
  p.append(price)
  products.append(p)
             
print(products)
for p in products:
  print(p[0],"價格是",p[1])

with open("products.csv","w",encoding="utf-8") as f: ##"w"=write
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
  f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
  for p in products:
    f.write(p[0]+","+str(p[1])+"\n")
```
### 記帳程式(任何情況)
```python=
import os
products=[]
if os.path.isfile("products.csv"): #檢查有無舊有檔案
  print("我找到檔案了")
  with open("products.csv","r",encoding="utf-8") as f: #"r"=read
    for line in f:
      if "商品,價格" in line:
        continue#跳過此回合
      name, price=line.strip().split(",")#strip去除多餘空白/換行
      print([name,price])
      products.append([name,price])
else: 
  print("找不到檔案")
     
      
while True:
  name=input("請輸入商品名稱")
  if  name=="q":
    break
  price=int(input("請輸入商品價格:"))
  p = [ ]
  p.append(name)
  p.append(price)
  products.append(p)
             
print(products)
for p in products:
  print(p[0],"價格是",p[1])

with open("products.csv","w",encoding="utf-8") as f: ##"w"=write
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
  f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
  for p in products:
    f.write(p[0]+","+str(p[1])+"\n")
```
## 基礎程式設計(10/22)(第七堂)
### 記帳程式函式寫法
```python=
import os
products=[]
def check_file(file_name):
  if os.path.isfile(file_name): #檢查有無舊有檔案
    print("我找到檔案了")
    with open((file_name),"r",encoding="utf-8") as f: #"r"=read
      for line in f:
        if "商品,價格" in line:
          continue#跳過此回合
        name, price=line.strip().split(",")#strip去除多餘空白/換行
        print([name,price])
        products.append([name,price])
  else: 
    print("找不到檔案")
  return products

def user_input(products):      
  while True:
    name=input("請輸入商品名稱")
    if  name=="q":
      break
    price=int(input("請輸入商品價格:"))
    products.append([name,price])
  return products #不知道=>傳入更改=>return

def print_list(products):
  for p in products:
    print(p[0],"價格是",p[1])

def write_file(file_name,products):
  with open(file_name,"w",encoding="utf-8") as f: 
 ##"w"=write
 #with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
    f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
    for p in products:
      f.write(p[0]+","+str(p[1])+"\n")

products=check_file("products.csv")
products=user_input(products)
print_list(products)
write_file("products.csv",products)

```
## 基礎程式設計(10/29)(第八堂)
### NOTE
#### 演算法特性 
①輸入:>=0個輸入值
②輸出:經過演算法處理後,至少有一個輸出結果
③明確性:演算法的每一個步驟都要有明確的定義
④有限性:在有限的步驟或時間內結束
⑤有效性:有效且具體可行

輸入+演算法=輸出(如同x經f(x)映射後的結果)
#### 時間複雜度
以O(BIG O)表示 e.g.:O(n^2),O(1),O(log n)...
時間複雜度並非以執行時間做為計算，而是以步驟次數作為計算(取最差的情況)
愛你N次
```python=
 n=int(input(""))
 for i in range(1,n+1):
   print("愛你",i,"次")

```
### 給定索引(座號)找名字
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
  for line in f:
    if "姓名"  in line:
      continue#跳過此回合
    else:
      name_list.append(line.strip())


n=input("請輸入姓名") #輸入名字=>編號
print( name_list.index(n)+2)


ind=int(input("請輸入編號") )#輸入編號=>名字
print( name_list[ind-2])


```
## 基礎程式設計(11/5)(第九堂)
### 循序搜尋1---數字查找(線性搜尋)
```python=
num_list=[6,1,5,7,3,9,4,2,8]
num=int(input("請輸入要找哪個數字") )#輸入數字
num_google=False
for i in num_list:
  if(num==i):
    num_google=True
    print("我找到了")
    print("在索引",num_list.index(num),"位置找到","花了",num_list.index(num)+1,"次搜尋")
    break
if(num_google==False):
  print("查無此號碼")
```

### 循序搜尋2---數字查找
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
  for line in f:
    if "姓名"  in line:
      continue#跳過此回合
    else:
      name_list.append(line.strip())
name_google=False
name=input("請輸入姓名") #輸入名字=>編號
for i in name_list:
  if(name==i):
    name_google=True
    print("我找到了")
    print("在索引",name_list.index(name),"位置找到","花了",name_list.index(name)+1,"次搜尋")
    break
if(name_google==False):
  print("查無此人")

```


### 循序搜尋3---名單持續更改(修改2))
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
  for line in f:
    if "姓名"  in line:
      continue#跳過此回合
    else:
      name_list.append(line.strip())
while True:
  name_google=False
  name=input("請輸入姓名") #輸入數字
  if(name=="q"):
    break
  for i in name_list:
    if(name==i):
      name_google=True
      print("我找到了")
      print("在索引",name_list.index(name),"位置找到","花了",name_list.index(name)+1,"次搜尋")
      break
  if(name_google==False):
    print("查無此人")

```
## 基礎程式設計(11/12)(第十堂)
### 二分搜尋
題目①:
有1數字空list,依序輸入數值資料如下:
16,2,81,34,67,47,53 共7個數字
請輸入一個數值,判斷此數值是否有在上
方數字數列中
狀況:
1.若數值有在數列中,請問數值在數字清
單中的哪個索引位置?並花了幾個步驟才
找到此數值。
2.若數值不在數列中,請列印查無此號碼
```csharp=
list_num=[16,2,81,34,67,47,53]
list_num.sort()
num=int(input("請輸入數值"))
left_index=0
right_index=len(list_num)-1
count=0
index=-1
print(list_num)
while(left_index<=right_index):
  count+=1
  mid=(left_index+right_index)//2
  if(num==list_num[mid]):
    index=mid
    break
  elif(num<list_num[mid]):
    right_index=mid-1
  elif(num>list_num[mid]):
    left_index=mid+1
if(index==-1):
  print("查無此號碼")
else:
  print("找到了")
  print("在索引",index,"位置找到")
print("共找了",count,"次")
```
題目②:
百貨公司舉辦周年抽獎活動,將顧客的
抽獎編號與姓名分別存在list中,使用者
輸入編號,程式會搜尋出該編號的姓名
並顯示,若查詢不到也會顯示無此編號
的訊息。
請以2分搜尋法進行中獎人查詢。
狀況:
1.若編號有在名單中,請問此人在清單
中的哪個索引位置?並花了幾個步驟才
找到此數值。
2.若人員不在名單中,請列印查無此人
```csharp=
num_name_list=[[256, 'A'], [731, 'B'], [943, 'c'], [389, 'D'], [142, 'E'], [645, 'F'], [829, 'G'], [945, 'H'], [371, 'I'], [418, 'j']]
num_name_list.sort()
no=int(input("請輸入中獎號碼"))
left_index=0
right_index=len(num_name_list)-1
count=0
index=-1
print(num_name_list)
while(left_index<=right_index):
  count+=1
  mid=(left_index+right_index)//2
  if(no==num_name_list[mid][0]):
    index=mid
    break
  elif(no<num_name_list[mid][0]):
    right_index=mid-1
  elif(no>num_name_list[mid][0]):
    left_index=mid+1
    
    

if(index==-1):
  print("查無此人")
else:
  print("找到了")
  print("在索引",index,"位置找到")
print("共找了",count,"次")
```
## 基礎程式設計(11/26)(第十一堂)
### Bubble Sort
```python=
list_num=[16,2,81,34,67,47,53]
list_sorted=[16,2,81,34,67,47,53]
print(sorted(list_sorted))
for i in range(0,len(list_sorted)):
  maxi_index=i
  mini_index=i
  for j in range(i,len(list_sorted)):
    if(list_sorted[j]>list_sorted[maxi_index]):
      maxi_index=j
    if(list_sorted[j]<list_sorted[mini_index]):
      mini_index=j
  c=list_sorted[mini_index]
  list_sorted[mini_index]=list_sorted[maxi_index]
  list_sorted[maxi_index]=c
  print(list_sorted)
```
### 改函式
```python=
def new_sort(list_sorted):
  for i in range(0,len(list_sorted)):
    maxi_index=i
    mini_index=i
    for j in range(i,len(list_sorted)):
      if(list_sorted[j]>list_sorted[maxi_index]):
        maxi_index=j
      if(list_sorted[j]<list_sorted[mini_index]):
        mini_index=j
    c=list_sorted[mini_index]
    list_sorted[mini_index]=list_sorted[maxi_index]
    list_sorted[maxi_index]=c
    print("第",i+1,"回合",list_sorted)


list_=[16,2,81,34,67,47,53]
print("排序前",list_)
print("排序後",new_sort(list_))
```
## 基礎程式設計(12/10)(第十二堂)
### NOTE
①概念:![](https://i.imgur.com/VlJvBh4.png)
(圖源:https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)
②時間複雜度:O(nlogn)
### 選擇排序
題目①:
動物園進行我是大明星的動物票選,票選
結果如下表。
將資料運用2維清單與插入排序進行以下
動作:

狀況:
1.將票數由小至大呈現每個動物的得票狀
況。並將排序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
3.並呈現誰是最高票的明星動物


| 明星候選人 | 票數 |
| ---------- | -------- |
|    長頸鹿        |     105     |
|     河馬   |         73 |
|     兔子  |          124|
|     猴子|          68|
| 獅子| 50|

```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
print("原始資料",vote_animals)
for i in range(len(vote_animals)-1):
  mini=i
  for j in range(i+1,len(vote_animals)):
    if(vote_animals[j][1]<vote_animals[mini][1]):
      mini=j
  change=vote_animals[i]
  vote_animals[i]=vote_animals[mini]
  vote_animals[mini]=change
  print("這是第%s次排序"%(i+1),vote_animals)
print("最高票動物:",vote_animals)
print("最高票:",vote_animals[-1])
```
題目②:
有1數字list,內部數值資料如下:
16,2,81,34,67,47,53 共7個數字
請利用選擇排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
```python=
num_list=[16,2,81,34,67,47,53]
for i in range(1,len(num_list)):
  position=i
  while position>0 and num_list[position]<num_list[position-1]:
    num_list[position],num_list[position-1]=num_list[position-1],num_list[position]
    #ac交換 a,c=c,a
    position-=1
print(num_list)


def insert_function(data):
  for i in range(1,len(data)):
    position=i
    while position>0 and data[position]<data[position-1]:
      data[position],data[position-1]=data[position-1],data[position]
      #ac交換 a,c=c,a
      position-=1
  return data
num_list=[16,2,81,34,67,47,53]
print("排序前資料:",num_list)
print("排序後資料:",insert_function(num_list))
```
## 基礎程式設計(12/17)(第十三堂)
### 插入排序
### NOTE
①概念:![](https://i.imgur.com/k2VDzAF.png)
②時間複雜度:O(n^2)
題目①:
有1數字list,內部數值資料如下:
41,33,17,80,61,5,55 共7個數字
請利用插入排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
for i in range(1,len(vote_animals)):
  position=i
  while position>0 and vote_animals[position][1]<vote_animals[position-1][1]:
    vote_animals[position],vote_animals[position-1]=vote_animals[position-1],vote_animals[position]
    #ac交換 a,c=c,a
    position-=1
print(vote_animals)
print()
```
題目②:
動物園進行我是大明星的動物票選,票選
結果如下表。
將資料運用2維清單與插入排序進行以下
動作:

狀況:
1.將票數由小至大呈現每個動物的得票狀
況。並將排序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
3.並呈現誰是最高票的明星動物


| 明星候選人 | 票數 |
| ---------- | -------- |
|    長頸鹿        |     105     |
|     河馬   |         73 |
|     兔子  |          124|
|     猴子|          68|
| 獅子| 50|

```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
def insert_function(data):
  for i in range(1,len(data)):
    position=i
    while position>0 and data[position][1]<data[position-1][1]:
      data[position],data[position-1]=data[position-1],data[position]
      #ac交換 a,c=c,a
      position-=1
    print("第",i,"回合",data)
  return data
print("排序前資料:",vote_animals)
print("排序後資料:",insert_function(vote_animals))
print(vote_animals[-1])




products=[]
with open("products.csv","r",encoding="utf-8") as f: #"r"=read
  for line in f:
    if "商品,價格" in line:
      continue
    name, price=line.strip().split(",")
    print([name,price])
    products.append([name,price])
    
```
## 基礎程式設計(12/31)(第十四堂)
### 合併排序(寫法1)
### NOTE
①概念:![](https://i.imgur.com/nBa53ff.png)
圖源:https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e
②時間複雜度:O(nlogn)
```python=
def merge(left,right):
    output=[]
    while (len(left) and len(right)):
        if (left[0]<=right[0]):
            output.append(left.pop(0))
        else:
            output.append(right.pop(0))
    if (len(left)):
        output=output+left
    
    if (len(right)):
        output=output+right
    print("此次合併狀況",output)    
    return output

def merge_sort(A):
    print("分割數列",A)
    if (len(A)<=1):
        return A
    mid=len(A)//2
    left=A[:mid]
    right=A[mid:]
    
    left=merge_sort(left)
    right=merge_sort(right)
    
    return merge(left,right)
data=[9,7,2,1,3,4,6,8]
print("原始串列",data)
```
## 基礎程式設計(1/7)(第十五堂)
題目:
有1數字list,內部數值資料如下:
9,7,2,1,3,4,6,8 共8個數字
請利用合併排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
### 合併排序(寫法2)
```python=
def merge(left,right):
  output=[0]*(len(right)+len(right))
  key_right=0
  key_left=0
  key_output=0
  while (len(left)-key_left and len(right)-key_right):
    if(left[key_left]>=right[key_right]):
      output[key_output]=right[key_right]
      key_right+=1
    else:
      output[key_output]=left[key_left]
      key_left+=1
    key_output+=1
  while(len(left)-key_left):
    output[key_output]=left[key_left]
    key_left+=1
    key_output+=1
  while(len(right)-key_right):
    output[key_output]=right[key_right]
    key_right+=1
    key_output+=1
  print("此次合併狀況",output)    
  return output    
def merge_sort(A):
    print("分割數列",A)
    if (len(A)<=1):
        return A
    mid=len(A)//2
    left=A[:mid]
    right=A[mid:]
    
    left=merge_sort(left)
    right=merge_sort(right)
    
    return merge(left,right)
data=[9,7,2,1,3,4,6,8]
print("原始串列",data)
print("後來串列",merge_sort(data))
```
## 總結
演算法比較


| 演算法                     | 時間複雜度 | 空間複雜度 | 概念類型 |
| -------------------------- | ---------- | ---------- | -------- |
| 選擇排序法(Selection Sort)|Ο(n^2)|Ο(1)|選擇|
| 插入排序法(Insertion Sort)|Ο(n^2)|Ο(1)| 插入|
| 氣泡排序法(Bubble Sort    |Ο(n^2)|Ο(1)|交換|
| 合併排序法(Merge Sort)    |Ο(nlogn) |Ο(n)+Ο(1)|合併|

心得:
我在這堂課學會了許多排序演算法，希望能在課外學得更多演算法
，以利於處理不同類型問題