wulaxiaohei 2020-05-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
1
| 5 | 4 | 6 | 9 | 3 | 8 |然后将现在的坐标 1
的数值进行一次交换
7进行交换位置1
经过此次交换后,得到以下数据。并且 1
也是最终位置
| 1
| 2 | 7
| 5 | 4 | 6 | 9 | 3 | 8 |
2
2
| 7 | 5 | 4 | 6 | 9 | 3 | 8 |2
, 就在最终位置。我们可以简单一点,直接不动2
也是最终位置2
| 7 | 5 | 4 | 6 | 9 | 3 | 8 |3
,当前位置第一是 7
7
| 5 | 4 | 6 | 9 | 3
| 8 |3
的数值进行一次交换7
进行交换位置
3
3
| 5 | 4 | 6 | 9 | 7
| 8 |4
,当前位置第一是 5
5
进行交换位置
4
4
| 5
| 6 | 9 | 7
| 8 |/** 记录开始时间 */ $timeStart = millisecond(); /** 生成一个 100 的随机数组,从 1 开始到 100 */ $sort = generateSort($num,1,$num); /** 记录结束时间 */ $timeEnd = millisecond(); /** 结束时间 - 开始时间,以后不再申明 */ var_dump(‘生成数组需要时间:‘. ($timeEnd - $timeStart) . " / ms");
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);
更多学习内容请访问:
如果要想让v2也进行排序,需要把k2和v2组装成新的类,作为k2,才能参与比较。// 1.1 告诉干活的人 输入流位置 读取hdfs中的文件。每一行解析成一个<k,v>。每一个键值对调用一次map函数