PHP实现-选择排序
2018-03-20 14:49 By
"Powerless"
2803
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
-
分布式服务限流 Posted on 2020-02-07 18:57
-
有状态服务VS无状态服务 Posted on 2020-02-07 18:18
-
企业级PAAS云平台几个关键问题和挑战 Posted on 2019-06-12 18:33
-
MySQL 单库后期分库策略 Posted on 2019-08-19 14:31
-
Redis七大经典问题 Posted on 2021-05-27 11:14
-
关于HTTPS的五大误区 Posted on 2020-02-02 01:10
-
为什么要测量尾部延迟 Posted on 2020-09-18 10:34
-
Git五分钟教程 Posted on 2019-11-18 22:24
评 论