2. 从业资格
  3. 对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分

对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分

练习题库2022-08-02  95
问题 对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分后得到的数组A为（  ）(非递减排序， 以最后一个元素为基准元素)。进行一趟划分的计算时间为（  ）。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)A.O(1)B.O(Ign)C.O(n)D.O(nlgn)
选项
答案 CC
解析 本题根据快速排序的过程，首先选定基准元素为最后一个元素（题干给出的要求），下面进行排序过程：
（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选项。
因为一趟划分的过程会与整个序列n个元素进行比较，因此一趟划分的时间复杂度为O(n)，第二空选择C选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2409353.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)