考点介绍：

在校招面试中,排序算法是经常被问到的。排序算法又比较多,很容易遗忘和混淆。有相当同学校招卡在排序的实现上,要么是核心代码实现不了,要么是实现方法串台。大厂的考察重点在快速排序等高级排序上。

本期分享的排序算法之高级排序，分为试题、文章以及视频三部分。

答案详情解析和文章内容可扫下方二维码或链接即可查看！

一、考点题目

1.以下哪种不是非稳定排序算法

A.归并排序
B.快速排序
C.堆排序
D.希尔排序

正确答案：A

2. 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

正确答案：对每个string做循环，记录里面每种字母的数量，然后加入到map中，最后map中相同键值的就是异位词。

3. 有一个公司有若干员工，要求设计一个签到系统来记录员工的签到顺序，并能够在nlogn的时间复杂度内利用尽可能少的辅助空间将签到的员工按照员工id进行排序。

正确答案：思路：在所有算法中只有堆排序和归并排序能够达到时间复杂度的要求，而堆排序对空间的要求又要优于归并排序，所以最后采用了堆排序来实现。

（答案点击下方链接或者扫海报二维码查看哦）

二、考点文章

1.堆的实现（图片演示+文字讲解）

虽然我们之前的介绍堆的时候是一个二叉树，但是我们实现堆的时候并不是按照传统的二叉树实现（传统的二叉树是用链的形式，即一个父节点存放两个子节点的引用）
为什么要这样说呢？

2.堆排序与快速排序比较

1. 10w 数据量两种排序速度基本相当，但是堆排序交换次数明显多于快速排序；10w+数据，随着数据量的增加快速排序效率要高的多，数据交换次数快速排序相比堆排序少的多。

3.四大高级排序

原理
1.先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1，处理结束。
2. 快排有一个特别需要注意的点，就是快排应该先从右边查找需要找的数

（扫下方海报二维码查看完整版）

三、考点视频

直接插入排序和最佳复杂度

更多资讯可搜索校招VIP小程序查看哦。
PC端链接：https://xiaozhao.vip/dTopic/detail/337
移动端链接：https://m.xiaozhao.vip/dTopic/detail/337