考点介绍：

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

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

一、考点题目

1、快速排序算法在序列已经有序的情况下的复杂度为（）

A.O(nlogn）

B.O(n^2)

C.O(n)

D.O(n^2 logn)

正确答案：B，快排在完全无序的情况下效果最好，时间复杂度为O（nlogn）,在有序情况下效果最差，时间复杂度为O(n^2)……

2、使用js实现数组的快速排序

解答：快速排序使用了冒泡+分治的思路。每轮从数组中取出一个数作为基准；在排序过程中，小于或等于基准数的全部放到基准的左边，大于基准的全部放右边；再对左边和右边依次进行上面两步......

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

A.正确

B.错误

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

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

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

5、快排算法在什么时候最慢？

解答：最坏情况下，是整个序列都已经有序或完全倒序。此时，快速排序退化为冒泡排序，要比较n2次才能完成……

6、使用荷兰国旗思想优化快速排序代码。

解答：在快速排序中可以使用荷兰国旗问题所采用的思想,即将每次划分的中间区域用来存放当前基数......

二、考点文章

1、【校招VIP】排序算法—快排

快速排序是对冒泡排序算法的一种改进，同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分，这种思路就叫做分治法......

2、【校招VIP】三个高级排序算法：快速排序、归并排序、堆排序

接下来的三个高级排序算法，是在实践中经常使用的算法，比起基于比较和交换的三个简单的排序算法，有更快的速度。快速排序和归并排序都属于递归排序算法，对于递归排序算法来说很重要的就是对递归树的理解......

3、【校招VIP】高级排序：快速排序

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列......

三、考点视频

用js实现数组排序

本题重点在于考查数据结构的排序算法，小讲分别使用了简单的冒泡排序和复杂的快速排序，从思路到实现……

更多资讯可搜索校招VIP小程序查看哦！

移动端链接：https://m.xiaozhao.vip/dTopic/detail/1260

PC端链接：https://xiaozhao.vip/dTopic/detail/1260