選擇排序(Select Sort）

選擇排序是重複進行「將數列中最小值，與左邊的值對調」，一直保持由小到大的數列。

選擇排序法使用線性搜尋(Linear Search)，比較次數是

• 第一次：n-1
• 第二次：n-2
• 第n-1次：1

import random

#從1-100中隨機讀取9個數字
nums = random.sample(range(1,100), 9)
print(nums)

# nums = [60, 50, 44, 82, 55, 77]

# i控制j的上限值
for i in range(8, 0, -1):
    #初始化變數0
    max = 0
    for j in range(1, i+1):
        if nums[j] > nums[max]:
            max = j
    nums[i], nums[max] = nums[max], nums[i]
    print("選擇排序的執行結果：",9-i,"次")
    for item in nums:
        print(item,' ',end="")

輸出結果：

[35, 77, 79, 23, 18, 92, 81, 90, 12]
選擇排序的執行結果： 1 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果： 2 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果： 3 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果： 4 次
35  77  12  23  18  79  81  90  92  
選擇排序的執行結果： 5 次
35  18  12  23  77  79  81  90  92  
選擇排序的執行結果： 6 次
23  18  12  35  77  79  81  90  92
選擇排序的執行結果： 7 次
12  18  23  35  77  79  81  90  92  
選擇排序的執行結果： 8 次
12  18  23  35  77  79  81  90  92

什麼是線性搜尋(Linear Search)？

線性搜尋是在陣列中搜尋數據的演算法，從陣列的前端開始依序查詢數據。也可以說，用暴力搜尋的方式在尋找數據。由於線性搜尋是從頭開始比較，當數據量大或資料在陣列的後方時，會耗費時間。當數據量為n時，執行時間是O(n^2)

def linearSearch(collection, t):
    for e in collection:
        if e == t:
            return True
    return False