PHP实现-选择排序
2018-03-20 14:49 By
"Powerless"
2938
0
2
思路分析
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
/*
* @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值较小时，选择排序比冒泡排序快
选择排序属于不稳定排序
View in WeChat
Others Discussion
-
2016年云计算热词 Posted on 2019-06-12 17:53
-
PHP没你想的那么差 Posted on 2021-12-17 15:40
-
Mysql联合索引的最左前缀匹配原则 Posted on 2018-08-25 15:00
-
巧用CAS解决数据一致性问题 Posted on 2019-03-07 11:55
-
分布式架构之「 数据分布」 Posted on 2019-11-14 10:00
-
PHP扩展ImageMagick安装 Posted on 2022-11-11 11:16
-
通过信鸽来解释HTTPS Posted on 2018-10-22 13:56
-
HTTP和HTTPS的区别 Posted on 2020-08-10 23:00
评 论