vlambda博客
学习文章列表

撰稿 | 康康哥

编辑 | 丽丽姐

本文由懂计算机、软件工程的博士师哥提供

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（   ）

A.  递归次数与初始数据的排列次序无关

B.  每次划分后，先处理较长的分区可以减少递归次数

C.  每次划分后，先处理较短的分区可以减少递归次数

D.  递归次数与每次划分后得到的分区处理顺序无关

本题考查：快速排序

快速排序，快速排序（Quicksort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

A选项，快速排序递归的次数与初始数据的排列顺序有关，若有序，则递归次数增多；递归的越多的说明执行的越多，时间复杂度越高，快排在序列基本有序的情况下的最坏时间复杂度为O(n^2)， A选项错误；

B、C选项，递归次数与每次划分后得到的分区处理顺序无关，BC选项错误；

故选 D

软工博士带你飞
考软工 · 看CS优化狮