快速排序平均时间复杂度是多少？软件设计师解析

题目

快速排序通过选取基准元素，将序列划分为左右两个子序列，再递归排序。通常情况下，快速排序的平均时间复杂度为（）。

A O(n log n)

B O(n)

C O(n²)

D O(1)

题目类型：原创高频考点题用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。

正确答案

答案解析

快速排序平均情况下每一层划分需要 O(n) 时间，递归深度大约为 O(log n)，因此平均时间复杂度为 O(n log n)。但如果基准选择很差，最坏情况下可能退化为 O(n²)。

选项分析

正确。快速排序平均时间复杂度为 O(n log n)。

错误。O(n) 通常不是比较排序的一般平均复杂度。

错误。O(n²) 是快速排序在极端不均衡划分下的最坏情况。

错误。O(1) 表示常数时间，与排序整个序列不符。

本题为什么容易错

这题容易因为记住“快速排序最坏 O(n²)”就直接选 C。考试问平均还是最坏，一定要看清。

先看结论

简短答案

快速排序的平均时间复杂度是多少，正确答案是 A（O(n log n)）。快速排序平均情况下每一层划分需要 O(n) 时间，递归深度大约为 O(log n)，因此平均时间复杂度为 O(n log n)。但如果基准选择很差，最坏情况下可能退化为 O(n²)。

解析

易混淆概念对比表

概念	本题判断	区别要点	记忆提示
O(n log n)	本题正确答案	正确。快速排序平均时间复杂度为 O(n log n)。	看到题干核心场景时优先联想到它
O(n)	本题干扰项	错误。O(n) 通常不是比较排序的一般平均复杂度。	看到该词不要急着选，先判断是否真正解决题干问题
O(n²)	本题干扰项	错误。O(n²) 是快速排序在极端不均衡划分下的最坏情况。	看到该词不要急着选，先判断是否真正解决题干问题
O(1)	本题干扰项	错误。O(1) 表示常数时间，与排序整个序列不符。	看到该词不要急着选，先判断是否真正解决题干问题

本题易混淆选项怎么区分

O(n)：错误。O(n) 通常不是比较排序的一般平均复杂度。
O(n²)：错误。O(n²) 是快速排序在极端不均衡划分下的最坏情况。
O(1)：错误。O(1) 表示常数时间，与排序整个序列不符。

复习

知识点详解

排序算法是软件设计师考试中需要结合场景理解的考点。围绕“快速排序的平均时间复杂度是多少”这类题目，复习时要先看题干描述的是概念定义、适用场景、作用效果，还是与其他选项的区别。本题的题干关键词是“快速排序通过选取基准元素，将序列划分为左右两个子序列，再递归排序。通常情况下，快速排序的平均时间复杂度为（）”，它指向的核心答案是 A（O(n log n)）。

备考速记

备考速记：题干如果强调“排序算法”中的关键目标，就先联想到排序算法；如果选项里出现 O(n)、O(n²)、O(1)，不要只看名称熟悉，要判断它们是否真正对应题干场景。

排序算法在排序算法场景中的作用

排序算法在本题中的核心价值，是解决“快速排序通过选取基准元素，将序列划分为左右两个子序列，再递归排序。通常情况下，快速排序的平均时间复杂度为（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

解题思路

这题问的是平均时间复杂度，不是最坏情况。快速排序在划分比较均衡时，类似把问题不断对半分，每层处理 n 个元素，总层数约 log n，所以平均是 O(n log n)。

考点定位

排序算法复杂度是软件设计师数据结构常考点。快速排序平均 O(n log n)，最坏 O(n²)，这两个要一起记。

易错提醒

平均复杂度和最坏复杂度不是一回事。
快速排序不稳定，归并排序通常稳定。
基准选择会影响快速排序性能。

备考提示

排序算法建议按平均复杂度、最坏复杂度、空间复杂度、稳定性四列整理。
看到“平均情况下”四个字，快速排序优先选 O(n log n)。

你可能还想了解

快速排序的平均时间复杂度是多少？
排序算法是什么？
排序算法在软件设计师考试中怎么考？
软件设计师排序算法题怎么理解？
快速排序平均时间复杂度怎么考？
软件设计师排序算法怎么考？

本文小结

本题核心考点是排序算法在排序算法场景中的判断和应用。遇到类似题目时，先看题干描述的目标，再判断哪个选项最符合场景；本题应选择 A（O(n log n)）。

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