试题出自试卷《2020年软件设计师考试上午真题（专业解析+参考答案）》

问题1选项
A.(1,2,8,7,3,5,6,4)
B.(1,2,3,4,8,7,5,6)
C.(2,3,1,4,7,5,6,8)
D.(2,1,3,4,8,7,5,6)

问题2选项
A.O(1)
B.O(lgn)
C.O(n)
D.O(nlgn)

第1题:C

第2题:C

第1题:

本题考查的是排序算法。

本题根据快速排序的过程，首先选定基准元素为最后一个元素（题干给出的要求），下面进行排序过程：
（1）基准元素4与另一端待排第一个元素2进行比较，满足非递减，不需要交换；
（2）基准元素4与另一端待排第一个元素8进行比较，不满足非递减，交换位置，此时序列为（2，4，7，1，3，5，6，8）；
（3）基准元素4与另一端待排第一个元素6进行比较，满足非递减，不需要交换；
（4）基准元素4与另一端待排第一个元素5进行比较，满足非递减，不需要交换；
（5）基准元素4与另一端待排第一个元素3进行比较，不满足非递减，交换位置，此时序列为（2，3，7，1，4，5，6，8）；
（6）基准元素4与另一端待排第一个元素7进行比较，不满足非递减，交换位置，此时序列为（2，3，4，1，7，5，6，8）；
（7）基准元素4与另一端待排第一个元素1进行比较，不满足非递减，交换位置，此时序列为（2，3，1，4，7，5，6，8）。
综上，本题第一空选择C选项。

第2题:

因为一趟划分的过程会与整个序列n个元素进行比较，因此一趟划分的时间复杂度为O(n)，第二空选择C选项。