快速排序的最坏时间复杂度

Question

如题所述

Answer 1

O(n^2)。
最坏情况发生在每次选择的基准元素都是当前子数组中的最大或最小元素时。在最坏情况下，快速排序的分区操作每次只能将数组划分为一个元素和n-1个元素两个子数组，进行n-1次分区操作完成排序。每次分区操作的时间复杂度是O(n)，遍历整个子数组确定基准元素的位置，最坏情况下的快速排序的总时间复杂度是O(n^2)。