上回說到冒泡排序，這次說說選擇排序。
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

基本思路

選擇排序的主要優(yōu)點(diǎn)與數(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值較小時，選擇排序比冒泡排序快。

選擇排序點(diǎn)圖

百聞不如一run （php實(shí)現(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)));

運(yùn)行結(jié)果

代碼運(yùn)行結(jié)果

參考
維基百科
Google搜索
等技術(shù)文檔