一、前言

相關(guān)知識來自《python算法設(shè)計與分析》。初級排序算法是指幾種較為基礎(chǔ)且容易理解的排序算法。初級排序算法包括插入排序、選擇排序和冒泡排序3種。雖然它們的效率相對于高級排序算法偏低，但是在了解初級排序算法之后，再去學(xué)習(xí)相對復(fù)雜的高級排序算法會容易許多。本文介紹選擇排序。

二、描述

選擇排序表示從無序的數(shù)組中，每次選擇最小或最大的數(shù)據(jù)，從無序數(shù)組中放到有序數(shù)組的末尾，以達到排序的效果。

選擇排序的平均時間復(fù)雜度是O(n2)，最好情況下的時間復(fù)雜度和最壞情況下的時間復(fù)雜度都是O( n2 )。另外，它是一個不穩(wěn)定的排序算法。選擇排序的過程很容易理解。如圖2-4所示，我們?nèi)砸赃f增排序的算法為例，先遍歷未排序的數(shù)組，找到最小的元素。然后，把最小的元素從未排序的數(shù)組中刪除，添加到有序數(shù)組的末尾。

因為最小的元素是1，所以1被添加到仍為空的有序數(shù)組末尾。

如圖2-5所示，我們繼續(xù)對剩余元素進行遍歷。這次，最小的元素是2。我們把它添加到已排序的數(shù)組末尾。由于已在有序數(shù)組中的元素必定小于未排序數(shù)組中的所有元素，所以這步操作是正確無誤的。

如圖2-6所示，重復(fù)上述步驟，當(dāng)未排序數(shù)組中只剩下一個元素時，把它添加到已排序的數(shù)組末尾，整個數(shù)組的排序就完成了。

三、代碼實現(xiàn)

選擇排序代碼：

nums = [5,3,6,4,1,2,8,7]
res = []　　　#用于存儲已排序元素的數(shù)組
while len(nums): #當(dāng)未排序數(shù)組內(nèi)還有元素時，重復(fù)執(zhí)行選擇最小數(shù)的代碼
 minInd = 0 #初始化存儲最小數(shù)下標的變量，默認為第一個數(shù)
 for i in range(1, len(nums)):
  if(nums[i] < nums[minInd]): #更新最小數(shù)的下標
    minInd = i
 temp = nums[minInd]
 nums.pop(minInd) #把最小數(shù)從未排序數(shù)組中刪除
 res.append(temp) #把最小數(shù)插入到已排序數(shù)組的末尾
print(res)

運行程序，輸出結(jié)果為：

[1,2,3,4,5,6,7,8] 

在程序中，第一個for循環(huán)中的i代表了有序數(shù)組之后的第一個位置，也就是未排序數(shù)組中的第一個位置。隨后，再使用一個for循環(huán)，在未排序數(shù)組中找到最小值的下標。首先，把最小值下標minInd初始化為未排序數(shù)組中第一個元素的下標。隨后，遍歷整個數(shù)組，遇到比目前的最小值更小的元素時，更新下標即可。找出最小值后，把它和未排序數(shù)組中的第一個元素交換位置，這時它就成了有序數(shù)組中的最后一個元素。

總結(jié)

以上就是要講的內(nèi)容，本文介紹了選擇排序的理論知識和代碼實現(xiàn)。選擇排序表示從無序的數(shù)組中，每次選擇最小或最大的數(shù)據(jù)，從無序數(shù)組中放到有序數(shù)組的末尾，以達到排序的效果。選擇排序的平均時間復(fù)雜度是O(n2)，最好情況下的時間復(fù)雜度和最壞情況下的時間復(fù)雜度都是O( n2 )。另外，它是一個不穩(wěn)定的排序算法。

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

最新評論