工作五年的游戏后端不知道排序算法的复杂度正常吗？

@changnet 你需要清楚，我没有说需要准备大量不确定的题的答案。这种问题质的评价，就是因为 OP 直接出的最水的一类的几乎没法更水的送分题（比较排序 naive(O^2)不 naive 的平均 O(n log n)），甚至因为结论过于容易被人死记硬背，而被许多人直球认为没资格做面试题。直接按这题的结果拒掉人，不太会怕误伤（至少比卡学历靠谱）。
如果这个层次的问题都要排除掉，那么算法差不多整个就不用问了（于是这人“熟练算法”也白写了，gg ）。

你提出“这么多种”×3 ，说明你对这个入门领域的问题层次以及难度梯度也是几乎毫无感知，所以才会把差距离谱的不同要求混为一谈。
对一般开发者来说，这里的结论完全不需要刻意记。稍微瞄过点算法入门的，都知道排序的平均复杂度形式上实在“正常”得过分，基本就 O(n^2)和 O(n log n)这两个答案二选一。因此甚至都不需要知道快速排序是个啥算法，这名字一听就不 naive ，所以是 O(n log n)。
退一步讲，现场“常识”就能推断出比较排序下限不可能少于 O(n)，掰指头算个 C(n,2)就该知道 naive O(n^2)，然后中间补个最常见的 log 而已。除了 O 本身的定义，就是高中数学（甚至……小学奥数）。这很难吗？
（排序默认都指时间复杂度，空间另说，稍微没那么水。）
你之前有提出要求理解算法的“效率”。对渐进复杂度这么容易复读（不刻意背就自觉记住）的形式都不去强调的话，如何去要人理解更普遍抽象或实际更妖孽的问题（比如卡常）呢？
你所谓的灵活应用字面上就比这里的问题实在难了不知道几个层次。

对职业开发者来说，见识少还是一层问题，还容易学习培训弥补，而少根筋是更劝退的。
比如上面有人说调用别人东西不要在乎这种问题，这是完全忽略了他的用户（可能是最终用户，可能是调用他的工作的开发者）的感受——他觉得锅全是他调用的，所以不管，顺手当做不存在实际直接甩给用户了。用户：exm ？？？

@FrankHB 下次发表自己逻辑的时候别捎带我哈，看不懂你在说啥，还是说自是自身情绪的表达。

@microxiaoxiao 你评估不到不意味着没影响，这时应该拉能够评估的人一起评估吧？另外，举一个你评估不到的例子没有说服力吧？

我举个更贴切的例子：很多年前还在写 Python 时，有人判断一个 key 是否在一个字典 d 里面是这样写的：key in d.keys() 。d.keys() 会返回一个包含字典所有 key 的列表，因此判断变成一个 O(n)操作；而 Python 字典本身是哈希表，正常 O(1)时间可以完成判断的，但要这样写：key in d 。当前者将将 O(1)操作变成 O(n)，导致数据处理很慢，消息队列经常堆积。按你的说法，这时应该找 Python 的作者？

还有人在 list 头部插入，list 是动态数组，头部插入效率很慢，要挪动后面的所有元素，这些常识调用前应该都要心里有数吧？若能做到心里有数，才有意识去探索更科学的解决方案：比如用 deque 双向队列这样的数据结构。

其实这个问题的答案不用讨论，就是不正常。不影响调用不是不学无术的理由。何况读了这么多年书，精益求精的道理应该都听过吧？可学可不学难道等于不学？这样高度有点低了。

其实我觉得他这还不如说忘了快速排序的实现了，一个完全不会算复杂度的开发很有可能会埋下性能的坑。

@hxysnail 看起来你没有太理解我表达的意思。我的完整意思是，每个人都无法穷尽所有细节，。如果一个人他关注的就是业务层面的，可能只要整体性能符合预期就行了，不符合再去分析瓶颈部分。你举的例子是建立在你相对熟练掌握下层细节的逻辑上。就以你这个例子再深入一点，系统层面调度也会对他有影响，是不是分时系统还是实时系统，还是古老的批处理，底层的硬件其实也会对软件有影响。就比如你的资源分配在寄存器和内存。系统分层次有个好处就在于屏蔽细节

@microxiaoxiao 所以这些都是要关注的呀，只是不用自己实现而已。掌握这些底层原理的好处就是写代码不容易给别人挖坑，不然调用出问题还不得人去解决？做底层的工程师一定不会帮你做上传的业务工程师解决的呀

我本人面试也比较喜欢聊数据结构和算法，倒不是想招个人进来写这些基础的东西，主要是想评估：

1. 候选人的逻辑思维能力如何？人是否聪明？
2. 候选人的编程能力如何？

一个连最基本的排序算法都玩不明白的人，你指望他干啥呢？只能干点调调接口，调调包的美其名曰业务开发吧？
一个连基本的排序算法都写不出来的人，你指望他能写啥代码呢？有啥堆啥吧？调通就了事吧？

当年在 BAT 做招聘，别说一个工作 5 年的后端开发，就是一个校招实习生，排序算法答不明白都是直接让 go home ，其他的都不用聊。

@unregister 抱歉让你感觉我在指责别人了，我说了这是我的困惑。没有指责候选的任何意图，可能我表达的不准确。

@shunia 比较排序的极限是 O(n*logn)，但快排最坏是 O(n^2)，还有最坏也是 O(n*logn)的算法

熟练算法跟数据结构这个 LeetCode 得刷够一定的量 才有勇气这么简历上写，简历第一印象 应该是把自己擅长的展示出来，求职者这么写的话实在是相当不明智，侧面估计也是为了简历不被 PASS 把，毕竟寒气已经传给每一个码农了。

@xsen 老哥说的对，文人相轻 码农之间的鄙视链一直都是，其实在老板眼里 就是个工具人 价值榨干就 35 劝退。后端的话，算法讲道理 也就是面试之前刷一刷，满足一下面试的形式主义 过场，毕竟谁都知道正式上班都是拧螺丝。

@hxysnail #147 搞笑，不妨这位大佬数数您工作这么多年项目中写了几个排序算法——只是单纯好奇

反正本人面试中从来不问数据结构和算法，就单纯的聊基础、项目与工程化。看重学习能力、意向、沟通能力，如果一个人连事情都说不明白，还谈何逻辑能力

不就是为了卡人而已嘛，还非得说的那么冠冕堂皇。国内又有多少岗位是深入涉及到算法的

@changnet 你之前的公然扯蛋，已经有些涉嫌侮辱业界和消费者智商了。路人还没资格反对你的观点了不是？
你再看看到底这里几个人不同意你的观点？你能以看不懂我说的搪塞，还能一个个全塞抹布过去？

给类似捧臭脚的：
做业务就做业务，不会写代码的就不要给写代码的捣乱。非得强行全栈的别指望好下场。
业界常识：这些工作之间互相不可替代。你可以不会其中一项，但是不会的活就得别人做。要么老实全当碉堡侠，剩下的相当于外包出去了。
再者，没被市场淘汰和正在被淘汰的厂，哪来那么空给在这种层次的问题上浪费时间“查接口”来糊弄。（我是有些奇怪有些厂不给加班费的超量工时是不是就是专预备给这种活了……）
退一步讲，作为专业人员，就是要有合理理由自认为“不会”，那也该直接按不合理需求怼回去。自己先怂了，达不到对方期望的这类岗位的一般常识性的要求，怪谁？

不好意思，上面 at 错了。上面应该 @microxiaoxiao 。不过下面一段通用。

@FrankHB 假期还搁这扯鸡巴呢，大晚上的。你反对就反对呗，多厉害似的。子写的多就有水平嘛？老子道德经五千字，嘻嘻

@FrankHB 你自己开个贴不香嘛，@那么多人有谁啥卵用，希望得到陌生人认可吗？我很认可你哟，嘿嘿，吊毛。还公然侮辱，天天在这扯什么大旗，吓唬谁呢，也要看你值得不值得呀。看我回复一般人怎么回复的，再来和我逼逼

@xsen 麻烦看清楚再回复，我说过了“倒不是想招个人进来写这些基础的东西”，做工程一定是站在巨人的肩膀上，调用成熟的解决方案，但这不代表工程师不需要懂

@xsen 我不知道你是不是想说“数据结构算法无用论”，合着大学的课都是开着玩的？那么多大厂面试都是问着玩儿？不过无所谓，你我可以保持自己的观点，不同而已。

@xsen 说“卡人”就没依据了。站在面试官的角度，巴不得每个候选人都合格，这样花在招聘的时间最少。别人怎么想我不清楚，但至少我个人是这样。有时面了好多，但都没有遇到合适的，是有挫败感的。

另外，确实大部分岗位都是不需要深入涉及算法的。但您可能对深入有点误解，排序算法应该只是极浅的算法吧。常用的那些数据结构，也是很基础的吧。

@FrankHB #136 确定瓶颈开始的做法从来都不是调用几次或者评估某个算法的实践复杂度
似乎您连压测都不知道