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

前言

首先我们玩的是比较经典的选择排序

选择排序也是我们本系列的第一个
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，当前位置第一是55进行交换位置4此时数据是这样的
| 1 | 2 | 3 |4|5| 6 | 9 |7| 8 |

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

实现一下代码，第一步#

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

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

第二步

进行排序，同时把排序性能耗时记录一下
tips： 在php当中，while要比for快一丢丢至于为什么这里用for，可能是博主不会用while吧

/*** 选择排序操作方法 - for* @param $sort* @param $n* @return mixed*/function get_lect_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_lect_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   =   millicond();/** 调用上面的排序方法 */$result =   get_lect_sort_for($sort,$num);/** 记录排序结束时间 */$sortend = millicond();var_dump('排序耗时：'. ($sortend - $sortstart) . " / ms");/** 验证是否有序 */$msg    =   issort($result) ? 'yes':'no';var_dump('排序是否正确 ? ：' . $msg);var_dump('本次排序大小历史年代表口诀：'. $num);

第四步

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

更多学习内容请访问：

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