每天學習一點兒演算法--選擇排序

來自專欄 Python愛好者

很多演算法只有在數據經過排序後才管用，比如我們之前學習的二分查找。當然，很多語言都內置了排序演算法，比如Python中的sort()函數和sorted()函數。我們可以直接調用內置函數完成排序，而不需要從頭編寫。

但是選擇排序是快速排序的基石，而快速排序是一種重要的演算法。所以，我們有必要對選擇排序有一個基本的了解。

在學習選擇排序之前，我們先回顧一下Python中的兩種基本數據結構：數組和鏈表。

數組和鏈表

數組的特點就是：

• 數組中的每個元素在內存單元中都是連續的

• 數組的元素從0開始編號，我們可以通過編號立即找到某個元素，因此數組的訪問元素速度為O(1)。

鏈表的特點就是：

• 鏈表中的元素可存儲在內存的任何地方，每個元素都存儲了下一個元素的地址，從而使一系列隨機的內存地址串在一起。

• 在鏈表中添加元素很容易，只需將其放入內存，並將其地址存儲在前一個元素中，因此鏈表的插入速度為O(1)

下面來對比一下數組和鏈表的基本操作的運行時間：

數組可以通過編號隨機訪問，因此讀取速度為O(1)。但在數組中插入（或刪除）元素，需要將後面的元素全部後移（或前移）。因此插入（或刪除）的速度為O(n)。

鏈表只能順序訪問，因此讀取速度為O(n)。但在鏈表中插入數據很簡單，只需要修改它前面的那個元素指向的地址。因此插入或刪除的速度為O(1)。

選擇排序

做了這麼多的鋪墊，其實和選擇排序也就只有半毛錢的關係。選擇排序的思路很簡單：

• 先找出最大（或最小）的元素放在第一位，其他不變
• 再找出次大（或次小）的元素放在第二位，其他不變
• 重複以上步驟，直至所有元素排列完畢

舉一個例子（從小到大排序）：

下面貼一個用Python實現的選擇排序：

def find_smallest(arr): """找出數組中最小的元素""" smallest = arr[0] # 存儲最小的元素 smallest_index = 0 # 存儲最小元素的索引 for i in range(1, len(arr)): if smallest > arr[i]: smallest = arr[i] smallest_index = i return smallest_indexdef selection_sort(arr): """對數組進行選擇排序""" new_arr = [] for i in range(len(arr)): smallest = find_smallest(arr) new_arr.append(arr.pop(smallest)) return new_arrarray = [5, 3, 3, 6, 2, 10]result = selection_sort(array)print("排序結果： ", result)

執行結果：

排序結果： [2, 3, 3, 5, 6, 10]

小結

• 需要存儲多個元素時，可用數組或鏈表
• 數組的元素時連續的；鏈表的元素是分開的
• 數組的讀取速度很快；鏈表的插入和刪除速度很快

每天學習一點點，每天進步一點點。

推薦閱讀：