建立一个网站的英文,服装品牌,虚拟机wordpress安装教程视频,给公司做网站风险这是八股文的知识#xff0c;但是中国人又个好的习惯#xff0c;当别人给你一块好吃的面包时#xff0c;你总想知道这个面包是怎么做的#xff0c;对于目前的IT行业来说#xff0c;不管这个做法你是被动的学习还是主动的探索#xff0c;你都要知道#xff0c;也必须要知…这是八股文的知识但是中国人又个好的习惯当别人给你一块好吃的面包时你总想知道这个面包是怎么做的对于目前的IT行业来说不管这个做法你是被动的学习还是主动的探索你都要知道也必须要知道。
高端的面试往往不会直接让你写代码我经历过一个面试要求纸上写一个图的数据结构这可能和我简历中的一条利用图的特性优化启动速度有关但是一般情况下我认为这个思想重于实践并且实践的复杂程度纸上是写不出来的有经验的面试官会给你算法但是重点是考虑你的思路和对模式算法套路的理解即应用。
比如说面试会要求说一下什么是冒泡排序或者快速排序并讲一下快速排序的大概过程。 为什么是这两个呢因为二者在不同时间复杂度中都具有代表性不知道时间复杂度怎么分析的可以看一下 算法-时间复杂度分析
再比如同样是O(n^2)的时间复杂度为什么推荐使用插入排序而不推荐冒牌排序这个问题则主要考查分析能力。
凡此种种都逃离不了对上面“做法”的扩展。
之前在拥有思想你就是高级、资深、专家、架构师 中提到过要提升编程思想数据结构和算法是必不可少的环节而今天我发现掌握分析算法的一些分析能力更加重要这就好比知道了怎么做面包还会担心没有面包吗
那如何分析一个排序算法呢
算法内存消耗
也就是常说的空间复杂度在排序算法中既有原地排序也有创建辅助空间排序的比如冒泡、插入等都是原地排序的原地排序是什么呢原地排序指空间复杂度是O(1)的排序算法。
这个指标怎么是分析一个算法的影响因素呢 比如相同时间复杂度的空间复杂度越小则应是我们选择的标准。
在这之前必须要明白的一点就是算法的性能除了算法本身实现之外都是时间和空间的转换来平衡的。
排序算法的执行效率
执行的效率一般讲以下几点
时间复杂度最好时间复杂度、最坏时间复杂度、平均时间复杂度
为什么要区分这三种时间复杂度呢
有些排序算法会区分为了好对比所以我们最好都做一下区分。对于要排序的数据有的接近有序有的完全无序。有序度不同的数据对于排序的执行时间肯定是有影响的我们要知道排序算法在不同数据下的性能表现
时间复杂度的系数、常数 、低阶
时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据所以在对同一阶时间复杂度的排序算法性能对比的时候我们就要把系数、常数、低阶也考虑进来。这其实是开发中比较重要的知识点分析算法的时候常以n做目标实际开发中则不然。
比较次数和交换或移动次数
基于比较的排序算法的执行过程会涉及两种操作一种是元素比较大小另一种是元素交换或移动这些操作都是需要考虑进去的
算法的稳定性
在排序算法中尤为明显如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变我们就可以说他是稳定的。反之则是不稳定的
稳不稳定又有什么关系呢
学习排序算法的时候都是用整数来举例但在真正软件开发中我们要排序的往往不是单纯的整数而是一组对象我们需要按照对象的某个 key 来排序
比如说我们现在要给电商交易系统中的“订单”排序。订单有两个属性一个是下单时间另一个是订单金额。如果我们现在有 10 万条订单数据我们希望按照金额从小到大对订单数据排序。对于金额相同的订单我们希望按照下单时间从早到晚有序。对于这样一个排序需求我们怎么来做呢
最先想到的方法是我们先按照金额对订单数据进行排序然后再遍历排序之后的订单数据对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难但是实现起来会很复杂。
借助稳定排序算法这个问题可以非常简洁地解决。解决思路是这样的我们先按照下单时间给订单排序注意是按照下单时间不是金额。排序完成之后我们用稳定排序算法按照订单金额重新排序。两遍排序之后我们得到的订单数据就是按照金额从小到大排序金额相同的订单按照下单时间从早到晚排序的。为什么呢
稳定排序算法可以保持金额相同的两个对象在排序之后的前后顺序不变。第一次排序之后所有的订单按照下单时间从早到晚有序了。在第二次排序中我们用的是稳定的排序算法所以经过第二次排序之后相同金额的订单仍然保持下单时间从早到晚有序。 ok ,了解答这些分析方法之后就可以分析算法了下面是常见的排序算法的各种分析 这个表中的时间复杂度一栏很明显最后三个排序的时间复杂度更优但是他们并不是我们常见的排序接下来分析一下这些特殊的算法看看以后有没有特殊的场景能使用它。
参考
排序算法及其时间复杂度
数据结构与算法之美
