数据结构 排序 思考题4

全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案

题目一：（表排序后的）物理排序过程的最坏情况是：

• A. 有2个环，每个包含N/2个元素

• B. 有N/2个环，每个环包含2个元素

• C. 只有1个环，包含了全部N个元素

• D. 不知道

B显然是最坏的情况（再想一下，如果有N个环呢，这说明每个环都是自己，根本不用排序，这是最好的情况）

题目二：设元素个数为N，整数进制为B，LSD的趟数为P，则最坏时间复杂度是

趟数*(桶个数+元素个数)

即O(P(N+B))

题目三：基数排序是稳定的算法。

• A. √

• B. ×

是对的。

在排序中，没有任何顺序交换，考虑次位优先排序，比如在择偶中，我们把好看放在第一要素，有钱放在第二要素，然后设置序列：{好看, 有钱}两项分别代表颜值和财富值，分别为0到9, {0,0}为特别丑的乞丐，{9,9}为*高富帅 

{5,5} {5,8} {5,3} {2,8} {3,8} {3,7}{3,7} {1,8} {1,2}  ……

桶排序的时候建立 10 个桶，然后依次扔进去，可以看到，{3,7} 和{3,7}在一个桶里，前面的在上面，后面的在下面。然后分别用10个主位桶来取，仍然是第一个{3,7}先被取到，然后是第二个。所以不会改变次序，属于稳定排序。

实在没题了就这样吧。一个比较表来镇楼。

全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案