算法与数据结构系列 ( 三 ) - 选择排序法 - Select Sort

浅浅的花香味﹌ 2023-05-21 05:59 120阅读 0赞

### 前言 ###

> 首先我们玩的是比较经典的选择排序  
> 选择排序也是我们本系列的第一个  `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 |

### 此后一直以此类推，直至到底 ###

--------------------

### 实现一下代码，第一步[\#][Link 1] ###

*  生成数组，同时把生成数组的耗时记录一下

/** 记录开始时间 */
    $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架构师教程目录大全，只要你看完保证薪资上升一个台阶（持续更新）][T3-T4_PHP]

**以上内容希望帮助到大家，**很多PHPer在进阶的时候总会遇到一些问题和瓶颈，业务代码写多了没有方向感，不知道该从那里入手去提升，对此我整理了一些资料，包括但不限于：分布式架构、高可扩展、高性能、高并发、服务器性能调优、TP6，laravel，YII2，Redis，Swoole、Swoft、Kafka、Mysql优化、shell脚本、Docker、微服务、Nginx等多个知识点高级进阶干货需要的可以免费分享给大家**，需要的可以加入**我的官方群[点击此处][Link 2]。

[Link 1]: https://link.zhihu.com/?target=https%3A//learnku.com/articles/43386%234328b2
[T3-T4_PHP]: https://zhuanlan.zhihu.com/p/102278033
[Link 2]: https://link.zhihu.com/?target=https%3A//jq.qq.com/%3F_wv%3D1027%26k%3D5kN6y8c