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

考点介绍：

快速排序是大厂和三四线公司校招的必考点。需要在理解原理的前提下，尽量把代码记忆下来。一方便理解双指标头尾双向进行的原因，另一方面对循环和递归的终止要准确掌握。

本期分享的内容分为试题、文章以及视频三部分。

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

一、考点题目

1、判断下列说法是否正确：就排序算法平均所用的辅助空间而言，堆排序、快速排序、归并排序的大小关系是堆排序<快速排序<归并排序。（）

A.正确

B.错误

正确答案：A堆的空间复杂度为1，快速排序为log2（n），归并为n......

2、下列排序算法中，哪个是稳定的排序算法？

A.选择排序

B.快速排序

C.归并排序

D.希尔排序

正确答案：C，选择排序在调整树的过程中改变节点的顺序导致不稳定，快排一个指针从前之后，一个从后至前，从后往前可能将多个小于基准数据的数原本先进入数组却放在了前面.....

3、快速排序的基本思路是什么？

解答：第一步:选取一个数作为基准(理论上可以随便选取)；第二步:分区,比基准值小的放左边,大的放右边,基准值放在两个分区之间；第三步:进行左边分区递归,以及右边分区递归.....

4、数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如1,2,3,2,2,2,5,4,2，数字2在数组中出现了5次，超过数组长度的一半，输出2。

解答：受快速排序的启发，在快速排序中，现在数组中选择一个数字，然后调整数组中的数字的顺序，使得比选中数字小的数字都排在它的左边，比选中数字大的数字都排在它的右边......

二、考点文章

1、数据结构-快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)……

2、【坐在马桶上看算法】算法3：最常用的排序——快速排序

上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O(N2)……

三、考点视频

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

本题是校招的常见考点之一，这里考察的是简单排序的直播插入排序。首先要对熟悉排序算法本身，不要把选择和插入搞混……