乘风原创程序

  • 算法与数据结构系列 ( 三 ) - 选择排序法 - Select Sort
  • 2020/5/6 11:26:05
  • 前言

    首先我们玩的是比较经典的选择排序
    选择排序也是我们本系列的第一个 o(n^2) 算法
    很多人认为最优的算法是 o(n log n) 级别的算法

    这样就衍生出了一个问题

     

    为什么要学习 o(n^2) 级别的算法?

    基础:

    o(n^2) 相对而言比较基础,由简入难。很多时候我们做项目,或者是做其他业务的时候。我们可能找不到最优的解决办法,但是我们肯定会一种最简单的办法。我们先将功能实现,再进行优化。可能相对而言,会有一些性能上面的问题。但是随着我们慢慢优化,我们也会慢慢找到新的,更优秀的方式

    容易实现:

    有些情况下,我们借用算法的思想去做项目的时候。因为本身达不到 o(n log n) 级别,那么这个时候,我们可以选择相对简单,和容易实现的级别。如: o(n^2)

    简单有效:

    某些特殊情况下,简洁有效

    由简入难:

    简单的排序算法思想,可以衍生出复杂的排序算法。这也是我写这个系列的原因,可能很多人,做了好几年的业务,也不一定用到算法。但是你的某些行为可能恰恰就是算法思想

    废话不多说,直接开始了

     

    插入排序,先简单了解一下思路

    首先我们有这么一段数据,我们需要将他们重新整合有序

    | 7 | 2 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |

    第一次排序

    • 用选择排序的思路就是先找到,最小数 1
      | 7 | 2 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |

    然后将现在的坐标 1 的数值进行一次交换

    7进行交换位置1

    经过此次交换后,得到以下数据。并且 1 也是最终位置

    1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |

    第二次排序

    • 然后我们再找到此时的最小数 2
      | 1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |
    • 我们发现 2, 就在最终位置。我们可以简单一点,直接不动
    • 经过此次交换后,得到以下数据。并且 2 也是最终位置
      | 1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |

    第三次排序

    • 然后我们继续在当前数据中继续寻找第三个,最小数 3,当前位置第一是 7
      | 1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |
    • 然后将现在的坐标 3 的数值进行一次交换
      7进行交换位置3
    • 此时数据是这样的
      | 1 | 2 | 3 | 5 | 4 | 6 | 9 | 7 | 8 |

    第四次排序

    • 然后我们继续在当前数据中继续寻找第四个,最小数 4,当前位置第一是 5
    • 5进行交换位置4
    • 此时数据是这样的
      | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 7 | 8 |

    此后一直以此类推,直至到底


     

    实现一下代码,第一步#

    • 生成数组,同时把生成数组的耗时记录一下
    /** 记录开始时间 */
    $timestart =   millisecond();
    /** 生成一个 100 的随机数组,从 1 开始到 100 */
    $sort =   generatesort($num,1,$num);
    /** 记录结束时间 */
    $timeend =   millisecond();
    /** 结束时间 - 开始时间,以后不再申明 */
    var_dump('生成数组需要时间:'. ($timeend - $timestart) . " / ms");
    

    第二步

    • 进行排序,同时把排序性能耗时记录一下
      tips: 在 php 当中,while 要比 for 快一丢丢
    • 至于为什么这里用 for,可能是博主不会用 while 吧
    /**
    * 选择排序操作方法 - for
    * @param $sort
    * @param $n
    * @return mixed
    */
    function get_select_sort_for($sort,$n){
      /** 将数据循环一次 */
      for($i = 0;$i < $n;$i++){
          /** 寻找数据中的最小值,同时跨过第一个元素 */
          for($j = $i + 1;$j < $n;$j++){
              /** 通过循环对比得到最小值 */
              if($sort[$i] > $sort[$j]){
                  /** 
                    * 将最小值和当前的第一个元素进行位置交换
                    * php 没有位置交换的函数,所以简单一点,先取出,再覆盖
                    */
                  $item = $sort[$i];
                  $sort[$i]   = $sort[$j];
                  $sort[$j]   = $item;
              }
          }
      }  
      return $sort;
    }
    

    while

    /**
    * 选择排序操作方法 - while
    * @param $sort
    * @param $n
    * @return mixed
    */
    function get_select_sort_while($sort,$n){
      $i = 0;
      while($i < $n){
          $j = $i + 1;
          while($j < $n){
              if($sort[$i] > $sort[$j]){
                  $item = $sort[$i];
                  $sort[$i]   = $sort[$j];
                  $sort[$j]   = $item;
              }
          $j++;
          }
      $i++;
      }
      return $sort;
    }
    

    第三步

    • 验证数组是否正确,记录时间
    /** 记录排序开始时间 */
    $sortstart   =   millisecond();
    /** 调用上面的排序方法 */
    $result =   get_select_sort_for($sort,$num);
    /** 记录排序结束时间 */
    $sortend = millisecond();
    var_dump('排序耗时:'. ($sortend - $sortstart) . " / ms");
    /** 验证是否有序 */
    $msg    =   issort($result) ? 'yes':'no';
    var_dump('排序是否正确 ? :' . $msg);
    var_dump('本次排序大小:'. $num);
    
    

    第四步

    • 基本就是这样,简简单单的完成了。
    • 如果有疑问,或者写错的地方,请在下面评论留言
    • 大家加油

    更多学习内容请访问:

    腾讯t3-t4标准精品php架构师教程目录大全,只要你看完保证薪资上升一个台阶(持续更新)