上一回，在前面已經對冒泡排序、直接插入排序、希爾排序做了說明分析（具體詳情可點擊下方的鏈接查看）。這回，將對(直接)選擇排序進行相關說明分析。

前幾篇鏈接列表：

1. 算法：排序算法之冒泡排序

2. 算法：排序算法之插入排序

3. 算法：排序算法之希爾排序

排序算法系列目錄說明

• 冒泡排序（Bubble Sort）

• 插入排序（Insertion Sort）

• 希爾排序（Shell Sort）

• 選擇排序（Selection Sort）

• 快速排序（Quick Sort）

• 歸併排序（Merge Sort）

• 堆排序（Heap Sort）

• 計數排序（Counting Sort）

• 桶排序（Bucket Sort）

• 基數排序（Radix Sort）

選擇排序（Selection Sort）

選擇排序(Selection sort)是一種簡單直觀的排序算法。

1. 基本思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的思想其實和冒泡排序有點類似，都是在一次排序後把最小的元素放到最前面，或者將最大值放在最後面。但是過程不同，冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇，每一趟從前往後查找出無序區最小值，將最小值交換至無序區最前面的位置。

2. 實現邏輯

• 第一輪從下標為 1 到下標為 n-1 的元素中選取最小值，若小於第一個數，則交換

• 第二輪從下標為 2 到下標為 n-1 的元素中選取最小值，若小於第二個數，則交換

• 依次類推下去......

3. 動圖演示

選擇排序演示

注：紅色表示當前最小值，黃色表示已排序序列，綠色表示當前位置。

具體的我們以一組無序數列｛20，40，30，10，60，50｝為例分解說明，如下圖所示：

選擇排序分解圖示說明

4. 複雜度分析

• 平均時間複雜度：O(N^2)

• 最佳時間複雜度：O(N^2)

• 最差時間複雜度：O(N^2)

• 空間複雜度：O(1)

• 排序方式：In-place

• 穩定性：不穩定

選擇排序的交換操作介於和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介於0和3(n-1)次之間。

比較次數O(n^2)，比較次數與關鍵字的初始狀態無關，總的比較次數N = (n-1) + (n-2) +...+ 1 = n x (n-1)/2。交換次數O(n)，最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。

5. 代碼實現

C版本：

選擇排序（C版本）

C++版本：

選擇排序（C++版本）

Java版本：

選擇排序（Java版本）

6. 優化改進

①二元選擇排序

改進思路：

簡單選擇排序，每趟循環只能確定一個元素排序後的定位。根據之前冒泡排序的經驗，我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進後對n個數據進行排序，最多隻需進行[n/2]趟循環即可。

②堆排序

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。具體的分析我們留到後面講堆排序時再詳細說明。

總結

選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

源碼地址：https://github.com/7-sevens/algorithm

下一篇預告：快速排序（Quick Sort）。欲知詳情，且聽下回分解。

微信公眾號

想要獲取更多精品技術乾貨，歡迎關注微信公眾號：開發者小黑屋