一道国外教材的算法题
Given an array A[0..n-1] and a small constant k. Suppose that array A at the beginning is " nearly sorted" such that for every element A[i] at most k elements to the left of A[i] are greater than A[i]. We define such a sequence to be k-near-sorted. For example the following sequence is 2-near-sorted:[8,1,2,7,3,4,5,6]
a. Write an efficient algorithm for completely sorting an array A which is k-near-sorted.
b. What is the time complexity of the algorithm in terms of n and k.
c. illustrate the algorithm for the sequence below, where k=2.
[8,1,2,7,3,4,5,6]
题目是说的什么意思啊，我都没看明白
k-near-sorted是一个已经基本有序数列，每个元素的左侧最多有k个元素比该元素大，
1 给出有效算法对该k-near-sorted数列排序
2 对于给定的n,k计算时间复杂度
3 用你的算法解释下面的序列，k=2 没人会吗....
页:
[1]