這次說說選擇排序。

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

基本思路

選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種。

來一張示例動畫圖看一下

紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

復雜度分析

選擇排序的交換操作介于 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間。
比較次數O(n^2），比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+…+1=n*(n-1）/2。

交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。

時間復雜度    О(n2)
最優時間復雜度    О(n2)
平均時間復雜度    О(n2)
空間復雜度    О(n) total, O(1) auxiliary

百聞不如一run （php實現選擇排序）

<?php/*** User: wujunze* Email: itwujunze@163.com* Blog: https://wujunze.com* Date: 2016/11/5**/function selectSort($arr) {//雙重循環完成，外層控制輪數，內層控制比較次數$len=count($arr);for($i=0; $i<$len-1; $i++) {//先假設最小的值的位置$p = $i;for($j=$i+1; $j<$len; $j++) {//$arr[$p] 是當前已知的最小值if($arr[$p] > $arr[$j]) {//比較，發現更小的,記錄下最小值的位置；并且在下次比較時采用已知的最小值進行比較。$p = $j;}}//已經確定了當前的最小值的位置，保存到$p中。如果發現最小值的位置與當前假設的位置$i不同，則位置互換即可。if($p != $i) {$tmp = $arr[$p];$arr[$p] = $arr[$i];$arr[$i] = $tmp;}}//返回最終結果return $arr;}var_dump(selectSort(array(4,66,3,23,91,36,88,6)));

代碼運行結果

以上內容希望幫助到大家，很多PHPer在進階的時候總會遇到一些問題和瓶頸，業務代碼寫多了沒有方向感，不知道該從那里入手去提升，對此我整理了一些資料，包括但不限于：分布式架構、高可擴展、高性能、高并發、服務器性能調優、TP6，laravel，YII2，Redis，Swoole、Swoft、Kafka、Mysql優化、shell腳本、Docker、微服務、Nginx等多個知識點高級進階干貨需要的可以免費分享給大家，需要請戳這里鏈接 或者關注咱們下面的專欄