涉及快排的一道面试题

缘起

在快速排序过程中，给出一个按照pivot排好第一轮的序列A.则判断哪些数可能是这个pivot.

分析

算法是如果是pivot的话,比它小的一定排在它前面,比它大的一定排在它后面,所以如果将A先排好序(记为B)的话,要知道某个数a是不是有可能成为pivot只需要看a在A中的索引是不是与B中的索引相等就行了,算法的时间复杂度是O(nLogn)的.