# 选择排序 ## 定义： > 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。  ## 代码： ``` /** * @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)，数据量很大的情况下性能表现并不是很理想