快捷導(dǎo)航

python排序算法之選擇排序

更新時(shí)間：2023年04月23日 10:03:19 作者：i阿極

這篇文章主要介紹了python排序算法之選擇排序,選擇排序表示從無序的數(shù)組中，每次選擇最小或最大的數(shù)據(jù)，從無序數(shù)組中放到有序數(shù)組的末尾，以達(dá)到排序的效果,需要的朋友可以參考下

一、前言

相關(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ù)組的排序就完成了。

在這里插入圖片描述

三、代碼實(shí)現(xiàn)

選擇排序代碼：

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)定的排序算法。

到此這篇關(guān)于python排序算法之選擇排序的文章就介紹到這了,更多相關(guān)python選擇排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: