On lzq ways

排序算法一 (冒泡,插入,选择)

2019-04-24  本文已影响6人  zhengqiuliu

平时开发中大多数都只是涉及到业务场景,对于底层的算法其实无需太多的关注,一是因为大多数框架目前已经这些基本的算法和能力,对于开发人员来说只需要会使用这些能力即可。可是这些基础知识又是如此重要,一是锻炼了个人的思维能力,还有就是这些上层的应用,都是基于这些基础知识来搭建的,如张无忌的九阳神功,练就了这门武功,再学习其它知识易如反掌。

最基础的排序算法分类:冒泡,插入,选择排序;快速排序,归并排序;桶排序,计数排序,基数排序。

先列出评价排序优劣的几个指标:

1,是否为原地排序算法。空间复杂度为O(1)

2,是否为稳定排序算法。相同的元素,排序不能产生顺序的变更

3,最好时间复杂度,最坏时间复杂度,平均时间复杂度。

从图可见冒泡排序和选择排序时间复杂度相同,但是为什么插入排序使用比冒泡排序要好?

实现代码算法的差别如下:

冒泡排序:

插入排序:

冒泡排序定义了临时变量进行交换,而插入排序只需要一次替换,3 Unit >  1 Unit。

虽然时间复杂度的阶数相同,但是系数不同,所以插入排序的效率要优于冒泡排序。

上一篇下一篇

猜你喜欢

热点阅读