目标

辨析快速排序的核心思想、复杂度、稳定性与正确性要点。

前置知识

建议先阅读快速排序正文，理解其算法步骤与复杂度分析。

作答方法

1. 阅读题面后先写下选择依据；
2. 提交答案后核对对错、正确答案和题解；
3. 做错的题重新作答，直到能说明其余选项为什么不成立。

选择题

答题进度已答 0/10正确 0

第 1 题

难度★★考点quick sort标识ds-drill-quick-sort-001

快速排序的核心思想是？

请选择一个答案

A相邻冒泡

B选枢轴 pivot 划分，左边小于等于 pivot、右边大于等于 pivot，再递归

C每次选最小

D分桶

第 2 题

难度★★考点quick sort标识ds-drill-quick-sort-002

快速排序的平均时间复杂度是？

请选择一个答案

AO(n)

BO(n log n)

CO(n²)

DO(n^1.5)

第 3 题

难度★★考点quick sort标识ds-drill-quick-sort-003

快速排序最坏情况退化为 O(n²) 的原因是？

请选择一个答案

A数组元素全相等

B枢轴总是最值，每层只减少一个元素，递归深度达 n

C使用了额外空间

D相邻交换

第 4 题

难度★★考点quick sort标识ds-drill-quick-sort-004

下列哪种优化能避免快排已有序时的退化？

请选择一个答案

A使用稳定排序

B三数取中或随机枢轴

C增加额外空间

D改为非递归

第 5 题

难度★★考点quick sort标识ds-drill-quick-sort-005

关于快速排序的稳定性，下列说法正确的是？

请选择一个答案

A稳定，因为原地排序

B稳定，因为递归划分

C不稳定，分区交换时等值元素可能跨过对方交换

D稳定性取决于枢轴选择

第 6 题

难度★★考点quick sort标识ds-drill-quick-sort-006

快速排序的额外空间复杂度（平均情况）是？

请选择一个答案

AO(1)

BO(log n)（递归栈）

CO(n)

DO(n log n)

第 7 题

难度★★★考点quick sort标识ds-drill-quick-sort-007

partition 函数返回的位置 p 满足什么性质？

请选择一个答案

Aa[p] 是全局最大值

Ba[l..p-1] <= a[p]，a[p+1..r] >= a[p]，a[p] 已就位

Ca[p] 是全局最小值

D前半段已排序

第 8 题

难度★★★考点quick sort标识ds-drill-quick-sort-008

快速排序对 [3,2,1,5,4]（选最后一个 4 为 pivot）第一次 partition 后，pivot 4 的位置是？

请选择一个答案

A下标 0

B下标 2

C下标 3

D下标 4

第 9 题

难度★★★考点quick sort标识ds-drill-quick-sort-009

快排的「小段转插入排序」优化目的是？

请选择一个答案

A提高稳定性

B减少小数组递归开销

C降低空间复杂度

D避免退化

第 10 题

难度★★★考点quick sort标识ds-drill-quick-sort-010

快速排序 vs 堆排序，下列说法正确的是？

请选择一个答案

A快排最坏 O(n log n)，堆排序最坏 O(n²)

B快排平均更快（缓存友好），但堆排序最坏不退化且原地

C快排稳定，堆排序不稳定

D快排空间 O(n)，堆排序 O(1)

答案总览（建议完成全部题目后查看）

1. 第 1 题：B
2. 第 2 题：B
3. 第 3 题：B
4. 第 4 题：B
5. 第 5 题：C
6. 第 6 题：B
7. 第 7 题：B
8. 第 8 题：C
9. 第 9 题：B
10. 第 10 题：B

完成清单

• 10 道题均在展开答案前独立作答；
• 每道错题都记录了错误原因；
• 能说明至少两道复杂度或稳定性题的完整推理过程。