十大经典排序算法学习记录
基于PHP实现十大经典排序算法,并分析其复杂度
冒泡排序
思路1
如图每次比较相邻两个,循环到某次没有改变为止.
PHP实现代码如下:
1 | $arr = [9,8,6,7,2,1,5,11,12,98,12,455,145,1557,54,475,15,488,4521,4754,85,5455,45554,565,45,45,4,5]; |
该思路实现排序时间复杂度为$O(n^2)$
思路2
循环记录最小值,计入结果集,计入后从原序列中删除,依次递推 时间复杂度仍为$O(n^2)$ ,该思路实际时选择排序
思路3
在思路1的基础上,每次执行一次循环后,我们实际已经知道了最大值,因此第二次循环时可以减少一次循环次数 循环次数为 n!
该思路实际也是为选择排序
1 |
|
思路4 插入排序
1 | /** |
将序列中的第一个值看作初始的有序序列,然后第二个值到结尾的序列看作无序序列
从头到尾从无需序列中依次取值,在有序序列中从头到尾依次扫描判断需要插入的位置
这种方式在待排序序列为逆序时效率最高,
示例代码:
1 | echo "<pre>"; |