五分钟学算法之经典算法题：排序算法（某东算法工程师比赛）

比眉伴天荒 2023-06-10 06:22 18阅读 0赞

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 程序员小吴

来源 | 五分钟学算法

### 题目描述 ###

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

A、直接选择排序

B、直接插入排序

C、堆排序

D、快速排序

### 题目分析 ###

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

![640?wx\_fmt=gif][640_wx_fmt_gif]

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

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

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

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

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

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

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

![640?wx\_fmt=png][640_wx_fmt_png]

### 更多内容 ###

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

专题地址：

https://www.cxyxiaowu.com/jingdiansuanfati

\---

以上，便是今日分享，觉得不错，还请点个在看，谢谢～

推荐阅读：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20230531/4a15d3201cb44c90a252d134cde3f141.png
[640_wx_fmt_gif]: /images/20230531/9d4df79c446b471a8363b093d390d9ab.png
[640_wx_fmt_png]: /images/20230531/bbce1c19e80f4e75908daf2fd8fe65a7.png
[640_wx_fmt_jpeg 1]: /images/20230531/a9a619e5352a429da9c1a0ec8b3580a8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关【系列】经典算法题：排序算法空间

击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=png][640_wx_fmt_png] 作者 | 程序...

╰半橙微兮°/ 2024年04月18日 22:48/ 0 赞/ 84 阅读

相关五分钟学算法之「分治算法」三步走

点击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![format_png][] 作者 | 江子抑来源 | 编程拯救世界

爱被打了一巴掌/ 2023年06月19日 11:06/ 0 赞/ 62 阅读

相关五分钟学算法之经典算法题：二分查找（某东校园招聘笔试真题）

今天分享一道简单的笔试题，题目来源于京东校园招聘笔试真题。你做出这道简单的题目需要花费多少东呢？题目描述有一个有序表为 \{1，5，8，11，19，22，31，35

淩亂°似流年/ 2023年06月13日 09:09/ 0 赞/ 16 阅读

相关五分钟学算法之经典算法题：排序算法（360校招笔试题）

今天分享的一道算法面试题来源于 360校园招聘2015届技术类笔试题。题目描述用某种排序方法对关键字序列（25,84,21,47,15,27,68,35,20）进

清疚/ 2023年06月13日 09:09/ 0 赞/ 107 阅读

相关五分钟学算法之经典算法题：排序算法（某东算法工程师比赛）

点击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | 程序

比眉伴天荒/ 2023年06月10日 06:22/ 0 赞/ 19 阅读

相关经典算法题：排序算法

点击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | 程序

深碍√TFBOYSˉ_/ 2023年06月08日 15:53/ 0 赞/ 23 阅读

相关算法系列之十大经典排序算法

算法系列之十大经典排序算法 1、有哪十大经典排序算法？ 2、冒泡排序 2.1、算法步骤 2.2、动画演

曾经终败给现在/ 2023年01月15日 08:26/ 0 赞/ 169 阅读

相关算法之经典排序算法

基本排序算法选择排序 > 首先，找出数组中的最小元素，并用首位的元素与它交换。然后，从后面找出次大元素，并用第二个位置的元素与它变换。重复此步骤，直到排序完整个数

我就是我/ 2022年06月06日 08:24/ 0 赞/ 328 阅读

相关【算法】之十大经典排序算法

一、排序算法介绍 -------------------- 1、排序的定义对一序列对象根据某个关键字进行排序。 2、排序相关术语稳定：如果a原

- 日理万妓/ 2022年05月19日 01:28/ 0 赞/ 244 阅读

相关经典排序算法

冒泡排序冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相

淩亂°似流年/ 2022年03月21日 02:29/ 0 赞/ 266 阅读