PHP实现-选择排序
2018-03-20 14:49 By
"Powerless"
2963
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 2019-11-14 10:00
-
PHP扩展ImageMagick安装 Posted on 2022-11-11 11:16
-
PHP7不兼容性 Posted on 2018-03-07 15:59
-
Redis各种数据类型的使用场景举例分析【三】 Posted on 2018-11-22 17:00
-
投票通过，PHP 8 确认引入 Union Types 2.0 Posted on 2019-11-18 22:22
-
PHP设计模式 - 委托模式 Posted on 2019-04-25 16:15
-
BASE原则 Posted on 2020-12-17 16:42
-
程序员年中考试题-段子版 Posted on 2021-06-23 15:57
评 论