问题
单项选择题
快速排序算法采用的设计方法是()。
A.动态规划法
B.分治法
C.回溯法
D.分枝定界法
答案
参考答案:B
解析:
快速排序通过一趟排序选定一个关键字介于“中间”的记录,从而使剩余记录可以分成两个子序列分别继续排序,通常称该记录为“枢轴”。
分治法也许是最广泛使用的算法设计方法,基本思想是把大问题的解分解成一些较小的问题,然后由小问题的解方便地构造出大问题的解。典型用法:Hanoi塔问题、比赛日程安排。
将大问题分解成小问题,为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。
可见,快速排序法正是分治法的一个应用。