介紹
排序雖然是一項基本操作，但卻是計算機應執行的最重要的操作之一。它是許多其他算法和過程(例如搜尋和合并)的基礎。了解不同的排序算法可以幫助您更好地了解不同算法背後的思想，并幫助您提出更好的算法。
在選擇排序算法排序通過找到未排序部分的最小值，然後與所述第一未排序的元件交換它的陣列。它是就地算法，這意味着您不需要配置設定其他清單。盡管速度很慢，但在記憶體有限的系統中，它仍被用作主要的排序算法。
在本文中，我們将解釋選擇排序的工作原理并在Python中實作它。然後，我們将分解算法的動作，以了解其時間複雜度。
選擇排序
那麼選擇排序如何工作？選擇排序将輸入清單分為兩部分，已排序的部分最初為空，未排序的部分最初包含所有元素的清單。該算法然後選擇所有未排序檔案的最小值，并将其與第一個未排序值交換，然後将排序部分增加一個。
此類的進階實作如下所示：
在上面的僞代碼中，argmin()是一個傳回最小值索引的函數。該算法使用變量i來跟蹤已排序清單的結束位置和未排序清單的開始位置。由于我們從沒有排序的項目開始并取最小值，是以，總是存在未排序部分的每個成員大于已排序部分的任何成員的情況。
第一行增加的值i，第二行找到最小值的索引，第三行交換這些值。交換之是以有效，是因為Python在将任何内容配置設定給左側之前先計算了右側，是以我們不需要任何臨時變量。
讓我們來看看它是如何工作的行動，包含以下元素的清單：[3, 5, 1, 2, 4]。
我們從未排序的清單開始：
3 5 1 2 4
未排序的部分包含所有元素。我們仔細檢查每個項目，并确定這1是最小的元素。是以，我們換1用3：
15 3 2 4
在其餘未排序的元素中[5, 3, 2, 4]，2是最低的數字。現在2，我們交換5：
1 23 5 4
此過程将繼續進行，直到對清單進行排序：
1 2 35 4
1 2 3 45
1 2 3 4 5
讓我們看看如何在Python中實作它！
實作
實作此算法的技巧是跟蹤最小值并交換清單的兩個元素。sort.py在您最喜歡的編輯器中打開一個名為的檔案，然後在其中輸入以下代碼：
現在，将一些代碼添加到檔案中以測試算法：
然後，您可以打開一個終端并運作以檢視結果：
該清單已正确排序！我們知道它是如何工作的，并且可以在Python中實作選擇排序。讓我們進入一些理論，看看它在時間方面的表現。
時間複雜度計算
那麼，選擇排序對清單進行排序需要多長時間？給定一個size數組，我們将采用一種方法并精确計算選擇排序算法所花費的時間n。代碼的第一行是：
這行不應該花費太多，因為它隻是設定函數堆棧。我們說這是一個常數-輸入的大小不會改變此代碼運作的時間。假設c1執行此行代碼需要執行操作。接下來，我們有：
這個有點棘手。首先，我們有兩個函數調用len()和range()，它們在for循環開始之前執行。len()CPython 的成本也與CPython的大小無關，CPython是Windows，Linux和Mac上的預設Python實作。的初始化也是如此range()。讓我們把這兩個叫做c2。
接下來，我們有for，即運作n - 1時間。這不是一個常數，輸入的大小确實會影響執行的時間。是以，我們必須将完成一個循環所需的時間乘以n - 1。
可以in說，評估營運商的成本是恒定的c3。這涵蓋了外部for循環。
變量配置設定也可以在恒定時間内完成。我們稱這個為c4：
現在，我們遇到内部for循環。它具有兩個常量函數調用。假設他們采取c5行動。
請注意，c5它與有所不同c2，因為range這裡有兩個參數，并且這裡要執行加法運算。
到目前為止，我們已經有了c1 + c2 + (n - 1) * (c3 + c4 + c5)操作，然後我們的内循環開始，将所有内容乘以…？好吧，這很棘手，但是如果仔細觀察，它會n - 2在第一個循環中花費時間，n - 3在第二個循環中花費時間，最後一次則花費1。
我們需要将所有内容乘以1到之間的所有數字的總和n - 2。數學家告訴我們，總和為(n - 2) * (n - 1) / 2。随時x在這裡閱讀有關1和任何正數之間的整數之和的更多資訊。
内循環的内容也将在固定時間内完成。讓我們把它需要的Python做的時候in，if，指派語句和變量交換占用的任意固定時間c6。
大家一起得到c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2。
我們可以簡化這個到：a * n * n + b * n + c，其中a，b和c代表評估常量的值。
這稱為O(n2)。那是什麼意思？總而言之，我們算法的性能基于輸入清單的平方大小。是以，如果我們将清單大小加倍，則将其排序所需的時間将乘以4！如果我們将輸入的大小除以3，則時間将減少9！
結論
在本文中，我們研究了選擇排序的工作原理并在Python中實作了它。然後，我們逐行分解代碼以分析算法的時間複雜度。
相關文章:Python中的語句、縮進和注釋 語句 用源代碼編寫的用于執行的指令稱為語句。Python程式設計語言中有不同類型的語句，例如Assignment語 […]...
在C / C++，Python，PHP和Java中交換兩個變量 如何在不使用庫函數的情況下交換兩個變量？ Python：在Python中，有一個簡單且文法簡潔的結構來交換變量 […]...
Python中的生成器Generator 先決條件: 疊代器 我們讨論生成器時涉及兩個術語。 Generator-Function： generator […]...
使用Python中的元類進行元程式設計 元程式設計看起來很時髦，但如果你曾經合作過的裝飾器或元類，你其實做過元程式設計。簡而言之，我們可以說元程式設計是操縱代碼的 […]...
使用Python進行滑鼠和鍵盤自動化 本文說明了如何使用Python中的pyautogui子產品自動執行滑鼠和鍵盤的移動。該子產品未預裝Python。因 […]...
用Python導入子產品 Python中的導入類似于C/C++中的#include header_file。通過使用import導入檔案 […]...
Numpy中的N維數組 ndarray Numpy中的N維數組(ndarray) Numpy中的Array是元素表(通常是數字)，所有元素都是相同類型 […]...
線性回歸(Python實作) 本文讨論了線性回歸的基礎知識及其在Python程式設計語言中的實作。 線性回歸是一種統計方法，用于對因變量與給定的 […]...