问题 单项选择题

快速排序算法采用的设计方法是()。

A.动态规划法

B.分治法

C.回溯法

D.分枝定界法

答案

参考答案:B

解析:

快速排序通过一趟排序选定一个关键字介于“中间”的记录,从而使剩余记录可以分成两个子序列分别继续排序,通常称该记录为“枢轴”。

分治法也许是最广泛使用的算法设计方法,基本思想是把大问题的解分解成一些较小的问题,然后由小问题的解方便地构造出大问题的解。典型用法:Hanoi塔问题、比赛日程安排。

将大问题分解成小问题,为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。

可见,快速排序法正是分治法的一个应用。

单项选择题
多项选择题