python排序演算法之選擇排序怎麼實現

一、前言

初級排序演算法是指幾個較為基礎且容易理解的排序演算法。初級排序演算法包括插入排序、選擇排序和冒泡排序3種。雖然它們的效率相對於高級排序演算法偏低，但是在了解初級排序演算法之後，再去學習相對複雜的高級排序演算法會容易得多。

二、描述

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

選擇排序的平均時間複雜度是O(n2)，最好情況下的時間複雜度和最壞情況下的時間複雜度都是O( n2 )。另外，它是一個不穩定的排序演算法。選擇排序的過程很容易理解。以遞增排序的演算法為例，我們先遍歷未排序的數組，在其中找出最小的元素，如圖2-4所示。然後，將未排序數組中最小的元素刪除，並將其新增至有序數組的末尾。

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

如圖2-5所示，我們繼續對剩餘元素進行遍歷。這次，最小的元素是2。我們把它加到已排序的陣列末尾。這個運算是正確的，因為已排序數組中的元素一定比未排序數組中的元素小。

如圖2-6所示，重複上述步驟，當未排序數組中只剩下一個元素時，把它加到已排序的數組末尾，整個數組的排序就完成了。

三、程式碼實作

選擇排序程式碼：

nums = [5,3,6,4,1,2,8,7]
res = []　　　#用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时，重复执行选择最小数的代码
 minInd = 0 #初始化存储最小数下标的变量，默认为第一个数
 for i in range(1, len(nums)):
  if(nums[i] < nums[minInd]): #更新最小数的下标
    minInd = i
 temp = nums[minInd]
 nums.pop(minInd) #把最小数从未排序数组中删除
 res.append(temp) #把最小数插入到已排序数组的末尾
print(res)

執行程序，輸出結果為：

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

在程式中，第一個for迴圈中的i代表了未排序數組中的第一個位置，即有序數組之後的第一個位置。隨後，再使用一個for循環，在未排序數組中找到最小值的下標。初始時，將最小值下標minInd賦值為未排序數組的第一個元素的下標。當遇到比當前最小值更小的元素時，只需更新索引並遍歷整個陣列。把找到的最小值和未排序數組中的第一個元素交換後，最小值就被放到了有序數組的末尾位置。

以上是python排序演算法之選擇排序怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！