### 基本原理
在要排序的一組數中，選出最小的一個數與第一個位置的數交換。然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。
### 動畫演示
### 算法步驟
1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。
3. 重復第二步，直到所有元素均排序完畢。
### 代碼實現
```
// 選擇排序（一）
function selectSort($arr)
{
$length = count( $arr );
if( $length <= 1 ) return $arr;
for($i = 0; $i < $length-1; $i ++) {
$min = $i;
for( $j = $i+1; $j < $length; $j ++) {
if( $arr[$min] > $arr[$j] ) {
$min = $j;
}
}
if( $min != $i ) {
$temp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $temp;
}
}
return $arr;
}
```
```
// 選擇排序（二）
function selectSort2($arr)
{
$length = count($arr); // 數組長度
for ($i = 0;$i < $length-1; $i++) { // 遍歷數組
$iTemp = $arr[$i]; // 暫存當前值
$iPos = $i; // 暫存當前位置
for ($j = $i + 1;$j < $length; $j++){ // 遍歷當前位置以后的數據
if ($arr[$j] < $iTemp) { // 如果有小于當前值的
$iTemp = $arr[$j]; // 暫存最小值
$iPos = $j; // 暫存位置
}
}
$arr[$iPos] = $arr[$i]; // 把當前值放到算好的位置
$arr[$i] = $iTemp; // 把當前值換成算好的值
}
return $arr;
}
// 調用測試
$arr = [3,1,13,5,7,11,2,4,14,9,150,6,12,10,8];
print_r(selectSort2($arr));
```
### 平均時間復雜度：O(n2)
在選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行 n-i 次比較(1 <= i <= n-1)，而每次交換最多需要3次移動，因此，總的比較次數 C = n (n - 1) / 2。
交換次數為O(n)，最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。交換次數比冒泡排序較少，由于交換所需CPU時間比冒泡排序所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。
原地操作幾乎是選擇排序的唯一優點，當空間復雜度要求較高時，可以考慮選擇排序；實際適用的場合非常罕見。
### 小結
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個 元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9， 我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩定的排序算法。
