频道栏目
首页 > 程序开发 > Web开发 > php > 正文
PHP简单选择排序(Simple Selection Sort)算法学习
2018-01-09 16:43:03           
收藏   我要投稿
基本思想:

通过 n - i 次关键字间的比较,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序。

算法实现:

//简单选择排序

//交换函数

function swap(array &$arr,$a,$b){

$temp = $arr[$a];

$arr[$a] = $arr[$b];

$arr[$b] = $temp;

}

//简单选择排序算法

function SelectSort(array &$arr){

$count = count($arr);

for($i = 0;$i < $count - 1;$i ++){

//记录第$i个元素后的所有元素最小值下标

$min = $i;

for($j = $i + 1;$j < $count;$j ++){

if($arr[$j] < $arr[$min]){

$min = $j;

}

}

if($min != $i){

swap($arr,$min,$i);

}

}

}

$arr = array(9,1,5,8,3,7,4,6,2);

SelectSort($arr);

var_dump($arr);

复杂度分析:

在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。

最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n^2),进行移动操作的时间复杂度为O(n)。

简单选择排序是不稳定排序。

点击复制链接 与好友分享!回本站首页
上一篇:PHP实现桶排序算法
下一篇:PHP排序算法系列之插入排序详解
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站