上一篇詳述了冒泡排序及其優化，有興趣的可以看看：
如何優化冒泡排序？
一、選擇排序（SelectionSort）
- 算法思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
- 排序過程：（默認升序）
- 從原序列中找到最小值，與數組第一個元素交換；
- 除第一個元素外，從剩下未排序的序列中找到最小值，與數組第二個元素交換；
- 共N-1趟，每趟都找到未排序的最小值，放到已排序的序列后面。
如圖所示，每一趟找到未排序的最小值，并放到有序序列的后面（即當前趟對應于數組中的第幾個元素）。
- java實現選擇排序：
?private?static?<T?extends?Comparable<??super?T>>?void?selectionSort(T[]?nums)?{
????????if?(null?==?nums?||?nums.length?==?0)?{
????????????throw?new?RuntimeException("數組為null或長度為0");
????????}
????????int?length?=?nums.length;
????????int?minValueIndex?=?0;
????????T?temp?=?null;
????????for?(int?i?=?0;?i?<?length?-?1;?i++)?{
????????????minValueIndex?=?i;
????????????for?(int?j?=?i?+?1;?j?<?length;?j++)?{
????????????????if?(nums[j].compareTo(nums[minValueIndex])?<?0)?{
????????????????????minValueIndex?=?j;
????????????????}
????????????}
????????????if?(minValueIndex?!=?i)?{
????????????????temp?=?nums[i];
????????????????nums[i]?=?nums[minValueIndex];
????????????????nums[minValueIndex]?=?temp;
????????????}
????????}
????}
復制代碼- 時間、空間復雜度及穩定性分析：
- 最好時間復雜度：最好情況是輸入序列已經升序排列，需要比較n*(n-1)/2次，但不需要交換元素，即交換次數為：0；所以最好時間復雜度為O(n^2)。
- 最壞時間復雜度：最壞情況是輸入序列是逆序的，則每一趟都需要交換。即需要比較n*(n-1)/2次，元素交換次數為：n-1次。所以最壞時間復雜度還是O(n^2)。
- 平均時間復雜度：O(n^2)。
- 空間復雜度：只用到一個臨時變量，所以空間復雜度為O(1)；
- 穩定性：不穩定排序。如序列3，5，3，1。第一次交換結果為1，5，3，3，我們發現原序列的第一個3排在了第二個3的后面。
二、插入排序（InsertSort）
算法思想：通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
排序過程：（默認升序）
InsertionSort 和打撲克牌時，從牌桌上逐一拿起撲克牌，在手上排序的進程相同。
舉例：
Input: {4, 3, 8, 5, 2, 6, 1, 7}。
首先拿起第一張牌, 手上有 {4}。
拿起第二張牌 3, 把 3insert 到手上的牌 {4}, 得到 {3 ，4}。
拿起第三張牌 8, 把 8 insert 到手上的牌 {3，4 }, 得到 {3 ，4，8}。
以此類推。
插入排序由N-1趟排序組成。對于p=1到N-1趟排序后，插入排序保證從位置0到位置p上的元素為已排序狀態。即插入排序利用了從位置0到p-1位置上已經有序的條件，將位置p上的元素向前查找適當的位置插入此元素。
如圖所示：在第p趟，我們將位置p上的元素向左移動，直到它在前p+1個元素（包括當前位置的元素）中的正確位置被找到。
java實現插入排序
private?static?<T?extends?Comparable<??super?T>>?void?insertSort(T[]?nums)?{
??????if?(null?==?nums?||?nums.length?==?0)?{
??????????throw?new?RuntimeException("數組為null或長度為0");
??????}
??????int?length?=?nums.length;
??????T?temp?=?null;
??????int?i?=?0;
??????for?(int?p?=?1;?p?<?length;?p++)?{
??????????temp?=?nums[p];
??????????for?(i?=?p;?i?>?0?&&?(temp.compareTo(nums[i?-?1])?<?0);?i--)?{
??????????????nums[i]?=?nums[i?-?1];
??????????}
??????????nums[i]?=?temp;
??????}
??}
復制代碼時間、空間復雜度及穩定性分析：
- 最好時間復雜度：最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需n-1次即可。即最好時間復雜度為O(n)。
- 最壞時間復雜度：最壞情況就是，序列是降序排列，那么總共需要n(n-1)/2次比較；移動次數（賦值操作）是比較次數減去n-1次（因為每一次循環的比較都比賦值多一次，共n-1次循環），即n(n-1)/2 - (n-1)；所以最壞時間復雜度為O(n^2)。
- 平均時間復雜度：O(n^2)。
- 空間復雜度：只用到一個臨時變量，所以空間復雜度為O(1)；
- 穩定性：穩定。
三、總結
? 選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種。選擇排序最好、最壞時間復雜度都為O(n^2)，空間復雜度為O(1)，屬于不穩定排序。
? 插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千；或者若已知輸入元素大致上按照順序排列，那么插入排序還是一個不錯的選擇。插入排序最好時間復雜度為O(n)、最壞時間復雜度為O(n^2)，空間復雜度為O(1)，屬于穩定排序。
