enter image description here enter image description here

讲解

由于本题中的N 值较小,因此我们在检查排序结果是否稳定时,可以用Program 3.2 中的这种比较笨的O(enter image description here) 算法。

Program 3.2 用笨方法判断稳定性

1 isStable(in, out)

2 for i = 0 to N-1

3 for j = i+1 to N-1

4 for a = 0 to N-1

5 for b = a+1 to N-1

6 if in[i] 与in[j] 的数字相等 && in[i] == out[b] && in[j] == out[a]

7 return false

8 return true

考察

本题中使用O(enter image description here) 的算法足以满足要求,但在处理N 更大的问题时,就需要多花些心思了。冒泡排序法属于稳定排序算法,因此输出永远都是“Stable”。然而,选择排序法是一种不稳定的排序算法,因此必须检查输出结果。其实,我们可以将选择排序的结果与冒泡排序的结果相比较,如此一来只用O(N) 便能解决问题。

参考答案

enter image description here enter image description here

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。