共用题干题快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了(1)算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n),则快速排序算法的最好和最坏情况下的时间复杂度为(2)。 空白(2)处应选择()
A: Θ(n)和Θ(nlgn)
B: Θ(n)和Θ(n2)
C: Θ(nlgn)和Θ(nlgn)
D: Θ(nlgn)和Θ(n2)
A: Θ(n)和Θ(nlgn)
B: Θ(n)和Θ(n2)
C: Θ(nlgn)和Θ(nlgn)
D: Θ(nlgn)和Θ(n2)
举一反三
- 快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了()算法设计策略。 A: 分治 B: 动态规划 C: 贪心 D: 回溯
- 以下关于快速排序算法的描述中,错误的是()。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为()时,排序效率最高(令序列的第一个元素为基准元素)。 A: 快速排序算法是不稳定的排序算法 B: 快速排序算法在最坏情况下的时间复杂度为0(nlgn) C: 快速排序算法是一种分治算法 D: 当输入数据基本有序时,快速排序算法具有最坏情况下的时间复杂度
- 以下关于快速排序算法的描述中,错误的是 (104) 。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素(12,25,30,45,52,67,85)构成,则初始排列为 (105) 时,排序效率最高(令序列的第一个元素为基准元素)。 104() A: 快速排序算法是不稳定的排序算法 B: 快速排序算法在最坏情况下的时间复杂度为O(nlgn) C: 快速排序算法是一种分治算法 D: 当输入数据基本有序时,快速排序算法具有最坏情况下的时间复杂度
- 在寻找n个元素中第k小元素问题中,如使用快速排序算法思想,运用分治算法对n个元素进行划分,应如何选择划分基准
- 对数组A=(2,8,7,1,3,5,6,4)用快速排序算法的划分方法进行一趟划分后得到的数组A为( )(非递减排序, 以最后一个元素为基准元素)。进行一趟划分的计算时间为( )。(软件设计师2020下半年) A: O(1) B: O(Ign) C: O(n) D: O(nlgn)