PHP排序算法之简单选择排序(Simple Selection Sort)实例分析

yipeiwu_com5年前PHP代码库

本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort)。分享给大家供大家参考,具体如下:

基本思想:

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

算法实现:

<?php
//简单选择排序
//交换函数
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);

运行结果:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

复杂度分析:

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

最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为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)

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

本文参考自《大话数据结构》,在此仅作记录,方便以后查阅,大神勿喷!

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于PHP相关内容感兴趣的读者可查看本站专题:《php排序算法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

相关文章

php简单定时执行任务的实现方法

本文实例讲述了php简单定时执行任务的实现方法。分享给大家供大家参考。具体实现方法如下: <?php ignore_user_abort(); set_time_lim...

简单谈谈PHP中的trait

前言 之前的一个同事换工作,在面试被问到了 PHP 的 trait 。因为没用过, 所以没答好,我大概是用过几次的,想了想整理了以下的总结。 trait trait 是在一些类(Cla...

PHP下通过系统信号量加锁方式获取递增序列ID

在网上搜了搜,有两个办法但都不太好:一个是简单的以进程ID+时间戳,或进程ID+随机数来产生近似的唯一ID,虽简单但对于追求“完美”的我不愿这样凑合,再说Apache2以后进程会维持相当...

PHP 解决session死锁的方法

今天在开发碰到个棘手的问题 。当异步请求后台处理一个大数据量操作时  请求其他控制器都没返回信息了。。起初以为是Ext 框架设置了ajax同步造成的。后来发现时session...

PHP 文件类型判断代码

何为MIME类型,它是设定某种扩展名的文件用一种应用程序来打开的方式类型,当该扩展名文件被访问时,浏览器会自动使用指定应用程序来打开。 多用于指定一些客户端自定义的文件名,以及一些媒体文...