五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

已知数据表 A 中每个元素距其最终位置 不远 ,为了节省时间,应该采取的算法是()

A、直接选择排序

B、直接插入排序

C、堆排序

D、快速排序

题目分析

我们在之前学习 希尔排序 算法的时候提及到,希尔排序进行到一定阶段(每个元素距离其最终位置不远时)一般都使用 插入排序 来收尾。

 一组动画彻底理解希尔排序

五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

如果知道这个很容易知道答案选 B 。

我们也可以通过分析这四个选项的时间复杂度来做判断。

选择排序:对于 n 个元素,每次都需要遍历 n 次(与元素偏移位置没有什么关系),时间复杂度为  O(n2)

插入排序:对于 n 个元素,如果每个元素距离其最终位置平均偏移  c 个单位,则每次比较 c 次,一共比较 n 趟,时间复杂度为 O(cn)。

堆排序:对于 n 个元素,使用堆排序无论元素的位置如何排放时间复杂度都是 O(nlog(n))。

快速排序:对于 n 个元素,即使每次选定的标定点很合适,它的最好时间复杂度也是 O(nlog(n))。

当然,如果你熟悉它们的最好情况下的时间复杂度也是能立马得出答案的。

五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

更多内容

你可以在电脑端访问我的个人博客下的专题 经典算法题 来阅读更多相关的面试题。

专题地址:

https://www.cxyxiaowu.com/jingdiansuanfati

以上,便是今日分享,觉得不错,还请点个在看,谢谢~
推荐阅读:
有了这套模板,女朋友再也不用担心我刷不动 LeetCode 了
图解 LeetCode 第 421 题:数组中两个数的最大异或值
互联网人职业发展之路:三年升高工,七年做架构,十年送外卖

五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

我还会在以下平台发布内容

GitHub 哔哩哔哩