選擇排序算法
選擇排序雖然是效率不是很高的排序算法曲掰，不過它在我們編程的時候還是會經(jīng)常使用，出場次數(shù)有時候可能要比效率更高的那些算法更高辜贵。
首先咱們通過一個動圖來了解選擇排序的過程：
通過這個動圖菱蔬，我們可以發(fā)現(xiàn)選擇排序的過程為：每次一輪遍歷都找到當前最小的元素并和未排序元素的第一個元素交換位置太闺。
接下來編寫代碼：
def sort(arr):
for j in range(len(arr)-1):
minIndex = j
for i in range(j+1,len(arr),1):
if(arr[i] < arr[minIndex]):
minIndex = i
arr[j],arr[minIndex] = arr[minIndex],arr[j]
def main():
arr = [3,1,2,4,6,7,8,9,5]
sort(arr)
print(arr)
if __name__ == "__main__":
main()
pass
執(zhí)行會輸出：
[1, 2, 3, 4, 5, 6, 7, 8, 9]
使用隨機數(shù)生成測試用例
通過上面我們已經(jīng)掌握了選擇排序代碼的編寫了，不過我們會發(fā)現(xiàn)枢贿，上面代碼的測試數(shù)組太簡單了殉农，只有1-9，這么一段數(shù)據(jù)集太少了并不能測試我們編寫的排序算法到底靠不靠譜局荚。
那如何才能靠譜呢超凳？
你應(yīng)該已經(jīng)想到了：加大測試集，增加測試次數(shù)耀态，是的轮傍，沒錯，當我們數(shù)據(jù)量大首装，測試集非常多的時候這段程序如果依然能正確的進行排序创夜，那我們就可以判斷它是一個正確的排序算法了。
好了仙逻，問題來了驰吓，如何才能生成大量的數(shù)據(jù)集（比如說一萬條）呢？
手寫肯定是不行系奉，所以咱們需要通過程序幫我們生成棚瘟，接下來我們分兩步完成生成隨機測試用例并測試。
- 使用隨機數(shù)生成大量測試集喜最；
- 測試程序是否已經(jīng)是排好序的狀態(tài)偎蘸。
第一步：隨機生成1萬條測試用例
使用random模塊我們就可以生成隨機數(shù)了
利用random模塊的random.randint(a,b)方法就可以生成從a到b的隨機數(shù)。
編寫代碼：
import random
def getRandomArr(num):
arr = []
for i in range(num):
arr.append(random.randint(0,num))
return arr
這段代碼可以生成num個從0到num的隨機數(shù)瞬内。
第二部：測試代碼編寫
接下來我們需要編寫一個函數(shù)檢測數(shù)組是否已經(jīng)是排好序的迷雪。
def isSorted(arr):
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
return False
return True
完整代碼：
import random
def sort(arr):
for j in range(len(arr)-1):
minIndex = j
for i in range(j+1,len(arr),1):
if(arr[i] < arr[minIndex]):
minIndex = i
arr[j],arr[minIndex] = arr[minIndex],arr[j]
def main():
arr = getRandomArr(10000) #測試一萬條數(shù)據(jù)
sort(arr)
print(isSorted(arr))#檢測是否排好序
#獲取隨機數(shù)
def getRandomArr(num):
arr = []
for i in range(num):
arr.append(random.randint(0,num))
return arr
#檢測是否已排序
def isSorted(arr):
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
return False
return True
if __name__ == "__main__":
main()
pass
這樣子我們就完成了一個選擇排序的編寫與測試啦。
繪圖查看選擇排序的算法執(zhí)行效率
僅僅掌握代碼怎么寫還不夠虫蝶，我們在深入一層章咧，接下來我們看看選擇排序的執(zhí)行效率，時間復(fù)雜度能真。
咱們在執(zhí)行代碼的時候發(fā)現(xiàn)當測試集數(shù)據(jù)量非常大的時候我們的程序非常慢赁严，其實選擇排序算是一種效率較低的排序算法扰柠，它的代碼執(zhí)行效率為：
要直觀的查看排序所花的時間我們只需要在排序獲取當前時間然后在排序之后獲取當前時間即可。
獲取當前時間使用到的是：datatime庫疼约，要獲取執(zhí)行的時間差卤档，需要四個步驟：
首先導(dǎo)入：
import datatime獲取開始時間，結(jié)束時間
時間相減
轉(zhuǎn)換格式
示例：
import datetime
startTime = datetime.datetime.now() #獲取開始時間
l = [0] * 10000000 #定義一千萬個為0的列表或者處理其他任務(wù)
endTime = datetime.datetime.now() #獲取結(jié)束時間
time1 = endTime - startTime #時間相減程剥，得到的是datetime.timedelta對象
#datetime.timedelta對象的'days', 'max', 'microseconds', 'min', 'resolution', 'seconds', 'total_seconds'這些屬性是可以調(diào)用的
print(time1)
print(str(time1 .seconds) + "." + str(time1 .microseconds//1000) + "s") #輸出時間差以秒為單位
在示例中定義了一千萬個為0 的列表劝枣，執(zhí)行的結(jié)果如下（機器不同時間可能有差別）：
0:00:00.064976
0.64s
通過這段代碼，我們就可以輸出執(zhí)行某段程序所消耗的時間了织鲸。
掌握了如何輸出時間差舔腾，我們就可以查看選擇排序的執(zhí)行效率了。
完整代碼：
import random
import datetime
def sort(arr):
for j in range(len(arr)-1):
minIndex = j
for i in range(j+1,len(arr),1):
if(arr[i] < arr[minIndex]):
minIndex = i
arr[j],arr[minIndex] = arr[minIndex],arr[j]
def main():
arr = getRandomArr(1000)
startTime = datetime.datetime.now()
sort(arr)
endTime = datetime.datetime.now()
#print(isSorted(arr))
expenseTime = endTime - startTime
print(str(expenseTime.seconds) + "." + str(expenseTime.microseconds//1000) + "s")
def getRandomArr(num):
arr = []
for i in range(num):
arr.append(random.randint(0,num))
return arr
def isSorted(arr):
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
return False
return True
if __name__ == "__main__":
main()
pass
使用matplotlib生成選擇排序執(zhí)行效率折線圖
直接輸出數(shù)值的方式還是不直觀搂擦，咱們使用圖表的方式展示選擇排序算法效率的折線圖稳诚。
import random
import datetime
import matplotlib.pyplot as plt
def sort(arr):
for j in range(len(arr)-1):
minIndex = j
for i in range(j+1,len(arr),1):
if(arr[i] < arr[minIndex]):
minIndex = i
arr[j],arr[minIndex] = arr[minIndex],arr[j]
def main():
timeList = []
#計算
l = [10,100,1000,2000,3000,4000,5000,10000]
for i in l:
arr = getRandomArr(i)
startTime = datetime.datetime.now()
sort(arr)
endTime = datetime.datetime.now()
expenseTime = endTime - startTime
expenseTime = float(str(expenseTime.seconds) + "." + str(expenseTime.microseconds//1000))
timeList.append(expenseTime)
#print(isSorted(arr))
plt.plot(l,timeList)
plt.show()
def getRandomArr(num):
arr = []
for i in range(num):
arr.append(random.randint(0,num))
return arr
def isSorted(arr):
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
return False
return True
if __name__ == "__main__":
main()
pass
