算法导论 思考题 8-5

a. 就是普通的排序

b. 2 1 3 5 4 7 6 9 8 10

c. 这个证明简单的吧。

A[i]<=A[i+k]可以得到

A[i]+A[i+1]+......A[i+k-1]<=A[i+1]+A[i+2]+......A[i+k]

充分性得证。

A[i]+A[i+1]+......A[i+k-1]<=A[i+1]+A[i+2]+......A[i+k]

两边各减去A[i+1]+A[i+2]+......A[i+k-1]

就得到A[i]<=A[i+k]

必要性得证。

所以是充要条件

d. 可以将数组分为k组，每组n/k个元素

第一组为A[1],A[1+k],A[1+2k],......

第二组为A[2],A[2+k],A[2+2k]......

......

对每组进行堆排序或者归并排序。

这样每组的时间为n/k*lg(n/k)，一共k组，所以总共的时间为nlg(n/k)

e. 提示已经很明显了，和d一样，可以将数组分为k组，每组n/k个元素

然后用6.5-9的算法进行k路合并

f. 懒得证明了。。。