• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
纆g 显示全部楼层 发表于 2021-10-25 20:09:57 |阅读模式 打印 上一主题 下一主题
本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort)。分享给大家供大家参考,具体如下:
基本头脑:
通过 n - i 次关键字间的比力,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序。
算法实现:
  1. <?php
  2. //简单选择排序
  3. //交换函数
  4. function swap(array &$arr,$a,$b){
  5.   $temp = $arr[$a];
  6.   $arr[$a] = $arr[$b];
  7.   $arr[$b] = $temp;
  8. }
  9. //简单选择排序算法
  10. function SelectSort(array &$arr){
  11.   $count = count($arr);
  12.   for($i = 0;$i < $count - 1;$i ++){
  13.     //记录第$i个元素后的所有元素最小值下标
  14.     $min = $i;
  15.     for($j = $i + 1;$j < $count;$j ++){
  16.       if($arr[$j] < $arr[$min]){
  17.         $min = $j;
  18.       }
  19.     }
  20.     if($min != $i){
  21.       swap($arr,$min,$i);
  22.     }
  23.   }
  24. }
  25. $arr = array(9,1,5,8,3,7,4,6,2);
  26. SelectSort($arr);
  27. var_dump($arr);
复制代码
运行结果:
  1. array(9) {
  2. [0]=>
  3. int(1)
  4. [1]=>
  5. int(2)
  6. [2]=>
  7. int(3)
  8. [3]=>
  9. int(4)
  10. [4]=>
  11. int(5)
  12. [5]=>
  13. int(6)
  14. [6]=>
  15. int(7)
  16. [7]=>
  17. int(8)
  18. [8]=>
  19. int(9)
  20. }
复制代码
复杂度分析:
在简单选择排序过程中,所需移动记录的次数比力少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。
最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大次序排列,则需要移动记录的次数最多为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程序设计有所帮助。

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作