问答题

阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
【说明】
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组 (可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1)中的每个元素，小于 A[q+1..r]中的每个元素。q的值在划分过程中计算。
2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
3．合并：快速排序在原地排序，故不需合并操作。

(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。
(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况(7) 。(最佳，平均、最坏)

【参考答案】

(4)O(nlgn)或O(log2n) (5)O(nlgn)或O(nlog2n)(6)O(n2) (7)最坏

<上一题 目录 下一题>
热门 试题

问答题
根据实体联系图，填充关系模式中的(a)、(b)、(c)和(d)，并给出训练记录和比赛记录关系模式的主键和外键。
问答题
【说明】 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图(a)所示。该遥控器共有4今按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如下图(b)所示。 图(b)中，类RomoteController的方法onPrcssButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号；command接口中on和off方法分别用于控制电器的开与关；Light中turnLight(int degree)方法用于调整电灯灯光的强弱，参数 degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中 sctChannel(int channel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。 【Java代码】 class Light{ 电灯类 public void trunLight(int degree){ 调整灯光亮度，0表示关灯，100表示亮度最大} }； class TV{ 电视机类 public void setChannel(int channel){ 0表示关机，1表示开机并切换到1频道} }； interface Command{ 抽象命令类 void on()； void off()； }； class RemoteController{ 遥控器类 protected Command []commands=new Command[4]； 遥控器有4个按钮，按照编号分别对应4个Command对象 public void onPressButton(int button){ 按钮被按下时执行命令对象中的命令 if(button % 2 == 0)commands[button]. on()； else commands[button]. off()； } public void setCommand(int button， Command command){ <u>(1) < u>=command； 设置每个按钮对应的命令对象 } }； class LightCommand implements Command{ 电灯命令类 protected Light light； 指向要控制的电灯对象 public void on(){light. trunLight(100)；)； public void off(){light. <u>(2) < u>；)； public LightCommand(Light light){this. light= light；)； }； class TVCommand implements Command{ 电视机命令类 protected Tv tv； 指向要控制的电视机对象 public void on(){tv. <u>(3) < u>；}； public void off(){tv. setChanne1(0)；}； public TVCommand(TV tv){this. tv= tv；}； }； public class rs { public static void main(String [] args){ Light light= new Light()； TV tv=new TV()； 创建电灯和电视对象 LightCommand lightCommand= new LightCommand(light)； TVCommand tvCommand=new TVCommand(tv)； RemoteController remoteController=new RemoteController()； 设置按钮和命令对象 remoteController. setCommand(0，<u> (4) < u>)； ... 此处省略设置按钮1、按钮2和按钮3的命令对象代码 } } 本题中，应用命令模式能够有效让类<u> (5) < u>和类<u> (6) < u>、类<u> (7) < u>之间的耦合性降至最小。
相关试题