python排序算法——選擇排序-創(chuàng)新互聯(lián)
- python排序算法——選擇排序
- 一、前言
- 二、描述
- 三、代碼實(shí)現(xiàn)
- 總結(jié)
一、前言
相關(guān)知識(shí)來自《python算法設(shè)計(jì)與分析》。初級(jí)排序算法是指幾種較為基礎(chǔ)且容易理解的排序算法。初級(jí)排序算法包括插入排序、選擇排序和冒泡排序3種。雖然它們的效率相對(duì)于高級(jí)排序算法偏低，但是在了解初級(jí)排序算法之后，再去學(xué)習(xí)相對(duì)復(fù)雜的高級(jí)排序算法會(huì)容易許多。本文介紹選擇排序。
二、描述選擇排序表示從無序的數(shù)組中，每次選擇最小或大的數(shù)據(jù)，從無序數(shù)組中放到有序數(shù)組的末尾，以達(dá)到排序的效果。
選擇排序的平均時(shí)間復(fù)雜度是O(n2)，最好情況下的時(shí)間復(fù)雜度和最壞情況下的時(shí)間復(fù)雜度都是O( n2 )。另外，它是一個(gè)不穩(wěn)定的排序算法。選擇排序的過程很容易理解。如圖2-4所示，我們?nèi)砸赃f增排序的算法為例，先遍歷未排序的數(shù)組，找到最小的元素。然后，把最小的元素從未排序的數(shù)組中刪除，添加到有序數(shù)組的末尾。
因?yàn)樽钚〉脑厥?，所以1被添加到仍為空的有序數(shù)組末尾。
如圖2-5所示，我們繼續(xù)對(duì)剩余元素進(jìn)行遍歷。這次，最小的元素是2。我們把它添加到已排序的數(shù)組末尾。由于已在有序數(shù)組中的元素必定小于未排序數(shù)組中的所有元素，所以這步操作是正確無誤的。
如圖2-6所示，重復(fù)上述步驟，當(dāng)未排序數(shù)組中只剩下一個(gè)元素時(shí)，把它添加到已排序的數(shù)組末尾，整個(gè)數(shù)組的排序就完成了。
選擇排序代碼：
nums = [5,3,6,4,1,2,8,7]
res = [] #用于存儲(chǔ)已排序元素的數(shù)組
while len(nums): #當(dāng)未排序數(shù)組內(nèi)還有元素時(shí)，重復(fù)執(zhí)行選擇最小數(shù)的代碼
minInd = 0 #初始化存儲(chǔ)最小數(shù)下標(biāo)的變量，默認(rèn)為第一個(gè)數(shù)
for i in range(1, len(nums)):
if(nums[i]< nums[minInd]): #更新最小數(shù)的下標(biāo)
minInd = i
temp = nums[minInd]
nums.pop(minInd) #把最小數(shù)從未排序數(shù)組中刪除
res.append(temp) #把最小數(shù)插入到已排序數(shù)組的末尾
print(res)
運(yùn)行程序，輸出結(jié)果為：
[1,2,3,4,5,6,7,8]在程序中，第一個(gè)for循環(huán)中的i代表了有序數(shù)組之后的第一個(gè)位置，也就是未排序數(shù)組中的第一個(gè)位置。隨后，再使用一個(gè)for循環(huán)，在未排序數(shù)組中找到最小值的下標(biāo)。首先，把最小值下標(biāo)minInd初始化為未排序數(shù)組中第一個(gè)元素的下標(biāo)。隨后，遍歷整個(gè)數(shù)組，遇到比目前的最小值更小的元素時(shí)，更新下標(biāo)即可。找出最小值后，把它和未排序數(shù)組中的第一個(gè)元素交換位置，這時(shí)它就成了有序數(shù)組中的最后一個(gè)元素。
總結(jié)
以上就是要講的內(nèi)容，本文介紹了選擇排序的理論知識(shí)和代碼實(shí)現(xiàn)。選擇排序表示從無序的數(shù)組中，每次選擇最小或大的數(shù)據(jù)，從無序數(shù)組中放到有序數(shù)組的末尾，以達(dá)到排序的效果。選擇排序的平均時(shí)間復(fù)雜度是O(n2)，最好情況下的時(shí)間復(fù)雜度和最壞情況下的時(shí)間復(fù)雜度都是O( n2 )。另外，它是一個(gè)不穩(wěn)定的排序算法。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
本文名稱：python排序算法——選擇排序-創(chuàng)新互聯(lián)
文章出自：http://m.jiaotiyi.com/article/dhocgc.html