【校招VIP】排序算法之高级排序- 校招VIP

考点介绍：

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

相关题目及解析内容可点击文章末尾链接查看！

一、考点试题

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

A.归并排序

B.快速排序

C.堆排序

D.希尔排序

解答：正确答案是 A

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等......

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

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

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

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

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

二、考点文章

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

虽然我们之前的介绍堆的时候是一个二叉树，但是我们实现堆的时候并不是按照传统的二叉树实现......

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

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

3.四大高级排序

先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1，处理结束......

三、考点视频

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

本题是校招的常见考点之一，这里考察的是简单排序的直播插入排序。首先要对熟悉排序算法本身，不要把选择和插入搞混。其次是针对每一轮的排序，考虑最少的比较次数是多少......