简述快速排序的思想，最好、最坏时间复杂度分别是多少?

核心考点

快速排序的分治思想、划分过程及时间复杂度分析，重点区分最好、最坏和平均情况。

参考答案(答题要点)

1.基本思想：快速排序采用分治策略。从待排序列中选一个元素作为基准(枢轴)，通过一趟划分将序列分成两部分，使左边元素不大于基准、右边元素不小于基准，基准放到最终位置;再对左右两个子序列递归进行快速排序。

2.划分过程：通常用双指针从两端向中间扫描，与基准比较并交换，直到两指针相遇，完成一次划分。划分后基准位置确定，且左右子序列分别递归。

3.最好时间复杂度：每次划分都较均匀，递归深度约为logn，每层划分总代价为O(n)，最好时间复杂度为O(nlogn)。

4.最坏时间复杂度：每次选到的基准都是当前序列最大或最小元素，划分极不均匀，递归深度为n，总代价为O(n^2)。常见于序列基本有序且固定选第一个或最后一个元素为基准。

5.平均时间复杂度：O(nlogn)。空间复杂度主要取决于递归栈深度，平均O(logn)，最坏O(n)。快速排序通常不稳定。

6.总结：快速排序核心是“选基准、划分、递归”。最好O(nlogn)，最坏O(n^2)，平均O(nlogn)。可通过随机选基准或三数取中降低最坏情况概率。

易错提醒

快速排序每趟划分不一定能确定所有元素最终位置，只能确定基准元素的最终位置。最坏情况不是“序列越乱越坏”，而是划分越不均匀越坏。时间复杂度分析要抓递归深度和每层代价。快速排序平均性能好，但最坏会退化。

今日小测

对序列基本有序时，若固定选第一个元素为基准，快速排序的时间复杂度最可能退化为多少?

答案：O(n^2)。