NOIP 普及组初赛 · NOIP 2009 普及组初赛试题第 15 题

选择题 · 答案 D · 考点：快速排序、基础算法、排序基础

题目

快速排序最坏情况下的算法时间复杂度为：

答案：D

快速排序基础算法排序基础

这题考快速排序最坏情况复杂度。拿到题先想：快排核心是选基准划分，最坏就是每次只划出一个元素，递归深度拉满到n，每层还要扫一遍n个元素，直接乘起来就是答案。

最容易把最坏情况记成平均情况的O(n log n)，或者误以为只要序列有序就一定是O(n)（那是归并或优化的快排）。其实经典快排若每次选到最大或最小值做基准，递归深度就是n，每层代价n，总代价n²。

快速排序的核心是“分治”：选一个基准（pivot），把数组分成比它小和比它大的两部分，然后递归。时间复杂度取决于两件事：递归深度和每一层要做的比较次数。

命题人喜欢拿“最坏情况”来测试你对算法本质的理解：平均情况往往靠直觉（O(n log n)），但最坏情况需要你真的推演递归过程。经典快排若每次选的基准都是当前序列的最大值或最小值，划分就极不平衡。

第 28 题· NOIP 2008 普及组初赛试题 · 答案 a[left]a[j]<valuea[j]<=valuevalue>a[j]value>=a[j]a[i]>valuea[i]>=valuea[i]=value;i+1,right,nFindKth(left,i-1,n);看解析 →
第 27 题· NOIP 2008 提高组初赛试题 · 答案 a[left];a[j]<valuea[j]<=valuea[i]>valuea[i]>=valuea[i] = value; i + 1,right,n FindKth(left, i – 1, n);看解析 →
第 17 题· NOIP 2009 普及组初赛试题 · 答案 D看解析 →
第 8 题· NOIP 2009 提高组初赛试题 · 答案 A看解析 →
第 7 题· NOIP 2011 提高组初赛试题 · 答案 C看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。