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. 懒得证明了。。。
转载请注明原文地址: https://ju.6miu.com/read-675686.html
