服务器之家

服务器之家 > 正文

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

时间:2019-10-26 16:09     来源/作者:LSGOZJ

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

基本思想:

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

算法实现:

  1. <?php 
  2.   
  3. //简单选择排序 
  4.   
  5. //交换函数 
  6. function swap(array &$arr,$a,$b){ 
  7.   $temp = $arr[$a]; 
  8.   $arr[$a] = $arr[$b]; 
  9.   $arr[$b] = $temp; 
  10. //简单选择排序算法 
  11. function SelectSort(array &$arr){ 
  12.   $count = count($arr); 
  13.   for($i = 0;$i < $count - 1;$i ++){ 
  14.     //记录第$i个元素后的所有元素最小值下标 
  15.     $min = $i; 
  16.     for($j = $i + 1;$j < $count;$j ++){ 
  17.       if($arr[$j] < $arr[$min]){ 
  18.         $min = $j; 
  19.       } 
  20.     } 
  21.   
  22.     if($min != $i){ 
  23.       swap($arr,$min,$i); 
  24.     } 
  25.   } 
  26. $arr = array(9,1,5,8,3,7,4,6,2); 
  27. SelectSort($arr); 
  28. 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)。

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

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

标签:

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
超A是什么意思 你好a表达的是什么
超A是什么意思 你好a表达的是什么 2019-06-06
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字 2019-06-05
返回顶部