教材32页代码2.2的copyFrom（)算法中，目标数组_elem[]是通过new操作由系统另行分配的，故可保证在物理上与来源数组A[]相互独立，若不能保证这种独立性，该算法需要做哪些调整？

对于几乎有序的向量，如教材代码2.26(60页)和代码2.27(60页)所示的起泡排序算法，都显得效率不足，比如，即便乱序元素仅限于A[0，√n)区间，最坏情况下仍需调用bubble()做Ω(√n)次调用，共做Ω(n)次交换操作和Ω(n^3/2)次比较操作，因此累计运行Ω(n^3/2)时间。

a)试改进原算法，使之在上述情况下仅需o(n)时间;

b)继续改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于A[n-√n，n)区间;

c)综合以上改进，使之在如下情况下仅需o(n)时间：乱序元素仅限于任意的A[m，m+√n]区间。

教材81页代码3.20中的List::selectionSort()算法，通过selectMax()在前缀子序列中定位的最大元素max，有可能恰好就是tail的前驱——自然，此时“二者”无需交换。针对这一“问题”，你可能会考虑做些“优化”，以期避免上述不必要的交换，比如将

a)以序列(1980，1981，1982，...，2011，2012;0，1，2，...，1978，1979)为例，这种情况共发生多少次？

b)试证明，在各元素等概率独立分布的情况下，这种情况发生的概率仅为1nn/n→0——也就是说，就渐进意义而言，上述“优化”得不偿失。