# 選擇排序 ## 定義： > 選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，將其放到已排序區間的末尾。  ## 代碼： ``` /** * @param $nums * @return mixed * 4 3 2 1 */ function selection_sort($nums){ if(count($nums) <= 1){ return $nums; } for($i=0;$i<count($nums);$i++){//控制最大循環次數,未排序區的第一個值 $min = $i;//假設最小的數的為未排序區的第一個數 for($j=$i+1;$j<count($nums);$j++){//拿未排序區的每一個值與最小數比較，總是記錄最小的數，這樣就可以找到未排序區的最小值 if($nums[$j] < $nums[$min]){ $min = $j; } } if($min != $i){//把未排序區的最小值與未排序區第一個數交換位置，也就是把未排序區中的最小值放到已排序區的后面 $temps = $nums[$i]; $nums[$i] = $nums[$min]; $nums[$min] = $temps; } } return $nums; } $nums = [4,3,1,2]; print_r(selection_sort($nums)); ``` ## 選擇排序的性能和穩定性 1. 時間復雜度： O(n^2) （n的平方） 2. 空間復雜度：原地排序算法 3. 算法穩定性：涉及非相鄰元素的位置交換，所以是不穩定的排序算法 ## 總結： > 綜合比較前面介紹的三個排序算法，時間復雜度都是一樣的，也都是原地排序，但是選擇排序是不穩定的排序算法，此外，插入排序和冒泡排序相比較，我們在將插入排序的時候講到，插入排序只需要一條語句，而冒泡排序需要三條，在同等條件下，或者數據量很大的情況下，插入排序性能是要由于冒泡排序的，所以綜合比較下來，三者的優先級是插入排序 > 冒泡排序 >> 選擇排序。但是三者的時間復雜度都是 O(n^2)，數據量很大的情況下性能表現并不是很理想