Question

有关算法快速排序的问题

题目是，假设含有n个元素的待排序数据a恰好是递减排列的，请举例说明调用快速排序算法QuikSort(a,0,n-1)递增排序的时间复杂度为O(n2)。 求本题解法，最好能简洁一些。

Answer 1

先说一下快速排序中最好的排序情况，最好的情况下，每次进行一次分区，我们会把一个序列刚好分为几近相等的两个子序列，这个情况也每次递归调用的是时候也就刚好处理一半大小的子序列。这看起来其实就是一个完全二叉树，树的深度为 O(logn)，所以需要做 O(logn) 次嵌套调用。但是在同一层次结构的两个程序调用中，不会处理为原来数列的相同部分。因此，程序调用的每一层次结构总共全部需要 O(n) 的时间。所以这个算法在最好情况下的时间复杂度为 O(nlogn)。
但是将递减数据调用快速排序进行递增排序，是快速排序中情况最差的，你可以试想一下，假设每次分区后都出现子序列的长度一个为 1 一个为 n-1，这会导致我们的表达式变成：
T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)
这是时间复杂度就是 O(n²)。

追问

老哥能简洁一下么，这是我们考试题，我想背下来分数好说

Answer 2

面试时最基本的排序算法