上回說到冒泡排序，這次說說選擇排序毙石。
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下颓遏。首先在未排序序列中找到最行炀亍（大）元素，存放到排序序列的起始位置叁幢，然后滤灯，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾力喷。以此類推刽漂，直到所有元素均排序完畢。
基本思路
選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關(guān)弟孟。如果某個元素位于正確的最終位置上贝咙，則它不會被移動。選擇排序每次交換一對元素拂募，它們當(dāng)中至少有一個將被移到其最終位置上庭猩，因此對n個元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中陈症，選擇排序?qū)儆诜浅：玫囊环N蔼水。
來一張示例動畫圖看一下
選擇排序的示例動畫录肯。
紅色表示當(dāng)前最小值趴腋，黃色表示已排序序列，藍(lán)色表示當(dāng)前位置论咏。
復(fù)雜度分析
選擇排序的交換操作介于 0 和 (n - 1） 次之間优炬。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間厅贪。
比較次數(shù)O(n^2）蠢护，比較次數(shù)與關(guān)鍵字的初始狀態(tài)無關(guān)，總的比較次數(shù)N=(n-1）+(n-2）+...+1=n*(n-1）/2养涮。交換次數(shù)O(n）葵硕，最好情況是，已經(jīng)有序贯吓，交換0次懈凹；最壞情況交換n-1次，逆序交換n/2次悄谐。交換次數(shù)比冒泡排序少多了蘸劈，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時尊沸，選擇排序比冒泡排序快威沫。
選擇排序點圖
<pre>
時間復(fù)雜度 О(n2)
最優(yōu)時間復(fù)雜度 О(n2)
平均時間復(fù)雜度 О(n2)
空間復(fù)雜度 О(n) total, O(1) auxiliary
</pre>
百聞不如一run （php實現(xiàn)選擇排序）
<?php
/**
* User: wujunze
* Email: itwujunze@163.com
* Blog: https://wujunze.com
* Date: 2016/11/5
*
*/
function selectSort($arr) {
//雙重循環(huán)完成，外層控制輪數(shù)洼专，內(nèi)層控制比較次數(shù)
$len=count($arr);
for($i=0; $i<$len-1; $i++) {
//先假設(shè)最小的值的位置
$p = $i;
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是當(dāng)前已知的最小值
if($arr[$p] > $arr[$j]) {
//比較棒掠，發(fā)現(xiàn)更小的,記錄下最小值的位置；并且在下次比較時采用已知的最小值進(jìn)行比較屁商。
$p = $j;
}
}
//已經(jīng)確定了當(dāng)前的最小值的位置烟很，保存到$p中颈墅。如果發(fā)現(xiàn)最小值的位置與當(dāng)前假設(shè)的位置$i不同，則位置互換即可雾袱。
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最終結(jié)果
return $arr;
}
var_dump(selectSort(array(4,66,3,23,91,36,88,6)));
運行結(jié)果
代碼運行結(jié)果
