时间:2021-05-26
本文实例讲述了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程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了java数据结构排序算法之树形选择排序。分享给大家供大家参考,具体如下:这里我们就来说说选择类排序之一的排序:树形选择排序在简单选择排序中,每次的
本文实例讲述了java数据结构与算法之简单选择排序。分享给大家供大家参考,具体如下:在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,
本文实例讲述了PHP排序算法之堆排序(HeapSort)。分享给大家供大家参考,具体如下:算法引进:在这里我直接引用《大话数据结构》里面的开头:在前面讲到简单选
本文实例讲述了PHP四种排序算法实现及效率分析。分享给大家供大家参考,具体如下:PHP的四种基本排序算法为:冒泡排序、插入排序、选择排序和快速排序。下面是我整理
本文实例讲述了JS中的算法与数据结构之常见排序(Sort)算法。分享给大家供大家参考,具体如下:排序算法(Sort)引言我们平时对计算机中存储的数据执行的两种最