PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
发布:smiling 来源: PHP粉丝网 添加日期:2018-06-06 10:47:45 浏览: 评论:0
本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort)。分享给大家供大家参考,具体如下.
基本思想:
通过 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;
- } //phpfensi.com
- }
- 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)。
简单选择排序是不稳定排序。
Tags: 实例分析 算法
相关文章
- ·PHP进制转换实例分析(2,8,16,36,64进制至10进制相互转换)(2018-07-26)
- ·php:树形结构的算法(2013-11-13)
- ·PHP冒泡排序算法详解(2014-07-23)
- ·php三种常用的排序算法(2014-08-02)
- ·php中单字符串匹配算法实例(2014-09-22)
- ·PHP中实现冒泡排序和快速排序算法示例(2015-04-04)
- ·最简单的php中字符串匹配算法教程(2015-04-06)
- ·PHP全排列算法实现程序代码(2015-04-08)
- ·PHP中简单实现数学组合算法(2015-04-08)
- ·php中字符串匹配KMP算法实现例子(2015-04-09)
- ·PHP中使用AES加密算法加密数据的例子(2015-04-13)
- ·PHP 冒泡/快速/选择/插入排序算法实例讲解(2015-12-24)
- ·用PHP实现URL转换短网址的算法示例(2016-07-27)
- ·php四种基础排序算法的运行时间比较(2016-08-25)
- ·PHP去重进行算法升级过程(2018-05-31)
- ·PHP排序算法之堆排序(Heap Sort)实例详解(2018-06-06)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)