思路分析
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
/*
* @param 选择排序法
* 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
* */
function selectSort($arr){
//双重循环完成，外层控制轮数，内层控制比较次数
$len = count($arr);
if ($len <= 1) {return $arr;}
for ($i = 0; $i < $len-1; $i++) {
$minIndex = $i;
// 找出i后面最小的元素与当前元素交换
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$minIndex] > $arr[$j]){
$minIndex = $j;
}
}
if ($minIndex != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$minIndex];
$arr[$minIndex] = $temp;
}
}
return $arr;
}
小结：
时间复杂度：O(n^2)
空间复杂度：O(1)
不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了
最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快
选择排序属于不稳定排序
评 论