下载APP
【简答题】
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
2.递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。
3.合并:快速排序在原地排序,故无需合并操作。
[问题2]
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度(用 O记号)。最佳情况为
(4)
,平均情况为
(5)
,最坏情况为
(6)
。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况
(7)
。 (最佳、平均、最坏)
举报
题目标签:
快速排序
时间复杂度
大于等于
参考答案:
参考解析:
刷刷题刷刷变学霸
举一反三
【单选题】在n个结点的线性表的数组实现中,算法的时间复杂度是O(1)的操作是 。
A.
访问第i(1<=i<=n)个结点和求第i个结点的直接前驱(1
B.
在第i(1<=i<=n)个结点后插入一个新结点< span="">
C.
删除第i(1<=i<=n)个结点< span="">
D.
以上都不对
查看完整题目与答案
【单选题】快速排序方法在 情况下最不利于发挥其长处。
A.
要排序的数据量太大
B.
要排序的数据中有多个相同值
C.
要排序的数据已基本有序
D.
要排序的数据个数为奇数
查看完整题目与答案
【判断题】()熔断的定电压,必须大于等于配电线路电压。
A.
正确
B.
错误
查看完整题目与答案
【单选题】027线压力高声光报警的设定值为大于等于()MPa。
A.
2.7
B.
2.8
C.
2.9
D.
3
查看完整题目与答案
【简答题】对快速排序来讲,其最好情况下的时间复杂度是_______,其最坏情况下的时间复杂度是________。
查看完整题目与答案
【判断题】工程结构的可靠指标应大于等于目标可靠指标。()
A.
正确
B.
错误
查看完整题目与答案
【判断题】设计温度大于等于450℃的压力容器称为高温容器。()
A.
正确
B.
错误
查看完整题目与答案
【单选题】二分图最大匹配问题的匈牙利算法的时间复杂度是____(请选择最准确项)
A.
B.
C.
D.
查看完整题目与答案
【判断题】在数据表初始状态是正序的情况下,快速排序算法的时间复杂度是O(n^2)。
A.
正确
B.
错误
查看完整题目与答案
【多选题】单笔受理金额大于等于100万元的高额收入审核权限()
A.
分公司业务支撑中心、财务共享中心分部
B.
市场部
C.
财务管理部
D.
省公司业务支撑中心、省市场部、省财务共享中心、省财务管理部
查看完整题目与答案