1. 基本思想

選擇排序（Select Sort）同樣是最基礎的排序算法之一，它的核心思想是：將要排序的序列分成有序和無序兩個部分，開始時有序部分為空，然后經過 n - 1 次遍歷，每次遍歷都在無序部分選取一個最值元素，然后放在有序部分中，到所有遍歷完成時有序部分已經擴展到整個區間了，即排序完成。

為了讓大家對選擇排序有更加清晰的認識，我們以下面這組數據作為例子來對選擇排序進行演示：

現在，我們需要對包含 8 個元素的序列 [1, 9, 2, 6, 0, 8, 1, 7] 進行升序（從小到大）排序。

按照選擇排序的思想，我們需要在序列的無序部分用某種手段去選出最值元素，我們在簡單選擇排序中通常用的都是順序查找法，然后將找到的最值元素通過交換，放到無須部分的邊界位置（靠近有序部分的那邊），實現有序部分的擴充。下面就是選擇排序的過程：

第一趟查找下來，0 作為無序部分的的最小元素被順序查找選擇到，然后交換到無序部分的邊界位置，形成了有序部分的第一個元素。

我們下面接著第二查找：

走完第二趟之后，我們可以看到 1 作為無序部分中的最小元素被交換到了無序部分的最右側，形成了已排序區間的第二個元素。

其實看到這里，大家都應該明白了，我們只要多再進行 $7?2$ 趟查找，就能將有序部分擴大到整個序列，完成選擇排序的過程，使得序列中所有的元素都是有序的。如果你還不懂這種思想的話，我#￥%&…

2. 代碼實現

選擇排序的代碼實現同樣非常好理解，在兩層 for 循環中，外層循環控制有序部分的右邊界，內層循環控制順序查找區間的范圍，if 條件句用于更新查找的最值，在完成一次查找后，還要將找到的值交換到邊界位置。實現代碼如下：

public void selectSort(int[] arr, int n) {for (int i = 0; i < n - 1; i++) {int min = i; // #1 最小值元素的下標for (int j = i + 1; j < n; j++) {if (arr[min] > arr[j]) {min = j; // #2 更新最小值的小標}}// #3 將最值元素交換到有序部分if (min != i) {int temp = arr[min];arr[min] = arr[i];arr[i] = temp;}} }

當然，簡單選擇排序的寫法肯定不止一種，下面還有一種鎖定下標的寫法，但是這種寫法沒有上面那種能明顯體現選擇排序的思想，而且容易被人誤認為是冒泡排序……

public void selectSort(int[] arr, int n) {// #1 要有序部分要拓展的位置for (int i = 0; i < n - 1; i++) {// #2 無序部分的范圍for (int j = i + 1; j < n; j++) {// #3 注意比較的下標值（區分冒泡排序）if (arr[i] > arr[j]) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}} }

我們可以從上面代碼得出，選擇排序的時間復雜度比較穩定，在最好和最壞情況都是$O(n^2)$。

在穩定性方面，像對這組數據[4, 6, 4, 1, 7]進行選擇排序的時候，會改變兩個 4 在排序前的相對前后順序。由此可知，選擇排序是一種不穩定的排序。

3. 優化

上面說到的選擇排序是簡單選擇排序，它的間復雜度是 $O(n^2)$。如果讓你對選擇排序進行優化，你會怎么做？我們不妨從選擇的方式來考慮，上面的選擇方式用的是普通的順序查找，我們需要想到比這個更快的。

優化方式1：雙指針法

我們可以在一次順序查找中，用兩個指針分別去尋找最大值和最小值，然后從有序部分從兩邊向中間拓展。雖然最終算法時間復雜度不變，但是確實是可以減少一半的比較的。下圖是一次選擇過程，可以理解一下。

注意：這種思想是沒有問題，但是因為有最大和最小兩個值，在后面在調換的時候，可能因為你寫的代碼處理不當而出現問題。

優化方式2：二分法

我們都知道，二分查找只能在有序的序列中使用，那么我們應該如何用上二分的思想呢？沒錯，就是用二叉樹！能滿足快速查找最值元素，而且最值元素被交換后的維護成本又相對比較低就只有堆了。

誒，這不就變成堆排序了嗎？是的，事實上堆排序也是選擇排序的一種，而且的它的效率很高，是為數不多的時間復雜度為 $O(nlogn)$ 的排序算法之一。我們遲點也會介紹堆排序，這里就不多說了。

---

又順手更了一波，別忘了點贊哦~

總結

以上是生活随笔為你收集整理的图解排序算法之谈「选择排序」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。