PHP简单选择排序(Simple Selection Sort)算法学习

yipeiwu_com5年前PHP代码库

本文实例为大家分享了PHP简单选择排序的具体代码,供大家参考,具体内容如下

基本思想:

通过 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);

复杂度分析:

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

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

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

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【宜配屋www.yipeiwu.com】。

相关文章

php判断对象是派生自哪个类的方法

本文实例讲述了php判断对象是派生自哪个类的方法。分享给大家供大家参考。具体实现方法如下: <?php $th = new Thread; //创建新对象 if (...

thinkphp框架实现删除和批量删除

thinkphp框架实现删除和批量删除

本文实例讲一下如何用thinkphp实现数据的删除和批量删除吧。 预期效果图:   原谅博主对照片的处理是如此的草率吧。。。 仍然是 通过MVC模式进行拆分: 首先是视图部...

php字符串截取函数用法分析

本文实例分析了php字符串截取函数用法。分享给大家供大家参考。具体分析如下: php自带的截取字符串的函数只能处理英文,数字的不能截取中文混排的,后面一个示例比较好用,第一个主要是给初学...

thinkphp多表查询两表有重复相同字段的完美解决方法

框架:thinkphp 版本:3.2.3 内容:查询语句 解决问题:重复字段问题 $Data = M('a')->where($where) ->Fiel...

PHP文件锁定写入实例解析

本文以实例讲述了PHP文件写入方法,以应对多线程写入,具体代码如下: function file_write($file_name, $text, $mode='a', $timeo...