考点介绍：

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

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

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

一、考点题目

1、有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}，是下列____排序算法一趟扫描的结果。

A.二路归并排序
B.快速排序
C.步长为 4 的希尔排序
D.步长为 2 的希尔排序

解答：B
如果是二路归并的话，那么第一趟结束后每四个都是有序的，如果是快速排序的话，第一个元素将会被放到一个最准确的位置，且第一个元素前面的都比它小，后面的都比它大......

2、为实现快速排序算法，待排序序列宜采用的存储方式是（）

A.顺序存储
B.散列存储
C.链式存储
D.索引存储

解答：A
快速排序中查询操作用的较多，而顺序存储 适用于频繁查询时使用； 链式存储适用于频繁地插入、删除、更新元素时使用.....

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

A.O(nlogn）
B.O(n^2)
C.O(n)
D.O(n^2 logn)

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

4、对数列 (25,84,21,47,15,27,68,35,20) 进行排序，元素序列的变化情况如下：

(1)25,84,21,47,15,27,68,35,20
(2)20,15,21,25,47,27,68,35,84
(3)15,20,21,25,35,27,47,68,84
(4)15,20,21,25,27,35,47,68,84

A.快速排序
B.简单选择排序
C.希尔排序
D.归并排序

解答：A
从（1）到（2）:取第一个数25，放到它应该在的位置，25左边的数都比25小，右边的都比25大.....

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

解答：快速排序使用了冒泡+分治的思路

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

二、考点文章

1、数据结构-快速排序

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

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

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

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

三、考点视频

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

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

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