NOIP 提高 2012 第一轮 第 5 题：第4层

题目

如果不在快速排序中引入随机化，有可能导致的后果是（   ）。

选项

• A. 数组访问越界
• B. 陷入死循环
• C. 排序结果错误
• D. 排序时间退化为平方级

答案

D

题解

考点定位

本题考「快排随机化」,对应大纲 4.1.3 排序（难度【2】）。

解题过程

不随机化 + 特定输入（如已排序 + 固定 pivot）⇒ 划分极度不平衡 ⇒ 时间退化为 O(n²)。结果仍正确、不会死循环/越界。

选 D。

易错提醒

① 随机化防的是「最坏时间」，不是正确性；② 与 2023 年同考点（时间退化为平方级）。