1、基礎排序演演算法

接下類，我們學習另外一類非常基礎的演演算法，即排序演演算法。
排序演演算法是電腦科學領域研究的非常深入的一類演演算法，排序這個動作本身也是非常重要的，
很多時候面對無需的資料，首先需要做的就是對他們進行排序。

---

排序演演算法——目的：讓資料有序。
排序演演算法——種類：種類也非常多，適用於不同的情景。
排序演演算法——思想：蘊含著重要的電腦科學中的演演算法設計思想。

---

我們即將學習2個簡單的排序演演算法：

• 1、選擇排序法
• 2、插入排序法

通過對這2個基礎的排序演演算法的學習，引申出更多東西，以打牢演演算法基礎；
後續學習更加高階和更加複雜的演演算法時，可以有充分的準備。

特別是插入排序法，由於它的一些特殊性質，後續我們甚至在一些高階排序演演算法的學習中，甚至需要用到這種
類似插入排序這樣的低階演演算法來進行一些優化。

---

2、選擇排序法演演算法設計思想

我們接下來首先來看選擇排序法。什麼是選擇排序法呢？它的思路本身很簡單。
比如說，給我們一些待排序的元素，我們如何將這些本來是亂序的元素從小到大排列好呢？
非常簡單，思路如下；

先在所有元素中將最小的元素拿出來
剩下的元素中，把最小的拿出來
剩下的元素中，把最小的拿出來
剩下的元素中，把最小的拿出來
……
只剩下一個元素，這個元素就是「剩下的元素中」最小的元素，將這最後一個元素拿出來

即：每次都選擇還沒處理的元素中最小的元素。
上述的思路就是選擇排序法。

我們現在建立一個陣列如下：

其中最小的元素是1：

拿出最小的元素1:

接著繼續拿出最小的元素，分別拿出2、3、4：

直到所有「剩餘的最小的元素」全部拿完，新的排序後陣列出現：

我們上述的圖片流程，我們的陣列從6、3、2、1、5、4
到1、2、3、4、5、6的這個過程。

其實是使用了一個額外的陣列空間，是從舊的陣列6、3、2、1、5、4的基礎上，新開闢了一個陣列。
之後每次從舊的陣列中找到剩下的元素中最小的元素，然後儲存到新開闢的陣列中……

這樣一個過程，其實這樣操作就佔用了額外的空間，也是一種空間上的浪費。

接下來，我們要做的一個比較重要的事情是，我們的選擇排序可否在原地完成？
這也是排序演演算法中非常重要的一個概念，即原地排序。

可以參考度孃的定義：原地排序

---

後續，我們會接觸較多原地排序的演演算法，隨著深入學習，我們會發現，有些演演算法可以用原地排序的方式實現；
但是對於另外一些排序演演算法，我們是無法原地排序實現的，必須藉助額外的空間。

我們今天即將實現的選擇排序就是一個可以原地排序的演演算法。

接下來，我們對選擇排序進行圖流程講解。

---

我們直接實現原地排序的演演算法程式碼，
其實思路比較簡單，我們每一輪找剩下的元素中最小的元素，我們只需要把我們找到的最小的元素直接放在陣列開頭的位置即可，即直接利用原來的陣列空間即可。
舉一個例子：
對於我們的陣列的索引i，它初始的時候指著我們的陣列索引為0的位置，表示我們現在想尋找排序之後的陣列的第0個元素的位置應該是誰？

為了找到這個最小的元素，我們可以再增加一個索引j，這個索引j從索引為0的位置出發，掃描一遍所有的元素，找到其中最小的元素。
之後我們再使用一個minIndex索引，記錄索引j找到的最小的元素所在的索引位置。

增加一個索引j，這個索引j從索引為0的位置出發，掃描一遍所有的元素:
j從0開始掃描：

j掃描結束：

j找到的最小的元素所在的索引位置，記為minIndex：

排序之後的陣列，它所對應的元素，應該是此時minIndex指向的1這個元素，現在i這個位置指向的元素是6這個元素，
我們所要做的事情，只需要把1和6這兩個元素交換位置，此時i=0這個位置的元素就已經是最小的那個元素了。
交換前：

交換後：

接下來，進一步，我們就可以做i=1的操作：

我們再做這一步的時候，我們就可以看到，每一步開始前，相當於arr[i……n)是未排序的（注意arr[i……n)是前閉後開）。
順便提一句：這裡的分析，用到了我們之前梳理過的迴圈不變數的知識。
迴圈不變數

從arr[1]到arr[n]都還沒有排序，但是arr[0]已經排序好了。

---

arr[i……n)是未排序的（注意arr[i……n)是前閉後開）；
arr[i……n)中的最小值要放到arr[i]的位置；而原本arr[i]位置的元素，我們放到陣列後面去，在後續的迴圈中繼續處理。即min(arr[i]……arr[n]）與arr[i]做交換。

j從arr[i]出發：

j掃描完整個陣列：

j掃描完整個陣列後，找到最小元素的索引，記作minIndex:

arr[i]與arr[minIndex]做交換：
交換前：

交換後：

此時arr[0]、arr[1]都已經排好序了。
下一輪迴圈開始前：

之後和前兩輪迴圈一樣，走完所有迴圈……
最後一輪迴圈過程如下：
j從arr[i]開始掃描：

j掃描完整個陣列：

j掃描完整個陣列後，找到最小元素的索引，記作minIndex:

arr[i]與arr[minIndex]做交換：
交換前：

交換後：

至此，整個陣列重新排序完成。
整個流程的關鍵是什麼呢？

1、arr[i……n)未排序，arr[0……i)已排序；
2、arr[i……n]中的最小值要放到arr[i]的位置。

其中的1，1、arr[i……n)未排序，arr[0……i)已排序；(注，這個就是我們我們的選擇排序法的迴圈不變數)
迴圈不變數

我們每一輪迴圈都在保持這個迴圈不變數，我們保持的方法就是2：
2、arr[i……n]中的最小值要放到arr[i]的位置。

這樣，我們就原地完成了選擇排序法。