小孩也能看懂的算法笔记-排序算法day1

算法虽然种类繁多，但是有没有发现算法应用有些共同点？

规划问题→找最优。
排名→找最多。
地图→找最短，最短距离、最短时间。
内容/商品推荐→找最近。

共同点显而易见：查找。

找到什么样的结果呢？
最近、最优、最多、最短。

怎么得出“最”的结果呢？
那不就是得把数据排序嘛！

经典教材里，排序算法和搜索，通常各有单独一章。

排序算法有哪些呢？
选择排序，快速排序，归并排序，插入排序，希尔排序，冒泡排序等等。

把1000个数字用不同算法排好，
所用的时间和脑力很不一样。

1次迈1个台阶和迈2个台阶，
爬100个台阶哪个更快？
爬1000个台阶呢？

不同排序算法的区别就是每次迈的台阶数不同，因此迈的次数和时间就不一样。
这是算法性能指标之一：时间复杂度，统一用O(n)表示。
其中：n是总共迈了多少次，迈一次的时间为O(1)，迈n次的时间是O(n)。

100个台阶每次迈1阶时，n是100
迈2阶时，n是100/2=50。

很多教材里说n是数据量，注意！这个数据量并不是数据个数。

各种排序算法都用多少时间？可以先简单了解下：
选择排序算法，O(n²)
归并排序/堆排，O(n log n)
特定条件下（整数+数值范围小）的基数排序/计数排序/桶排序：O(n)

还有的排序算法是变化的：
快速排序，最坏O(n²)，最快和平均都是O(n log n)，

今天先写这么多，手机打字，累了累了。
我是fivebliss，欢迎点赞收藏关注！
数据结构有啥用