已知一個幾乎有序的數(shù)組，幾乎有序是指忘巧，如果把數(shù)組排好順序的話饶米，每個元素移動的距離可以不超過k桨啃，并且k相對于數(shù)組來說比較小。請選擇一個合適的排序算法針對這個數(shù)據(jù)進行排序檬输。
給定一個int數(shù)組A优幸，同時給定A的大小n和題意中的k，請返回排序后的數(shù)組褪猛。
測試樣例：
輸入：[2,1,4,3,6,5,8,7,10,9],10,2
返回：[1,2,3,4,5,6,7,8,9,10]
class ScaleSort {
public:
void swap(vector<int> &A, int i, int j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
// 調(diào)整堆，adjusting_node羹饰，是當前待調(diào)整的節(jié)點
void adjust_heap(vector<int> &A, int adjusting_node, int last_node)
{
int parent = adjusting_node, child = 2 * adjusting_node + 1;
int curr_value = A[adjusting_node];
while(child <= last_node){
if(child < last_node && A[child] > A[child+1]){
++child;
}
if(curr_value > A[child]){
A[parent] = A[child];
parent = child;
child = 2*parent + 1;
}
else{
break;
}
}
A[parent] = curr_value;
}
vector<int> sortElement(vector<int> A, int n, int k) {
// write code here
if (n < k){
return A;
}
// 初始化大小為K的最小堆伊滋，由A的前K個元素組成
vector<int> heap(A.begin(), A.begin()+k);
for(int i=k/2-1; i>=0; i--){
adjust_heap(heap, i, k-1);
}
// 對錢n-k個數(shù)進i行排序
int idx = k;
while(idx<=n-1){
A[idx - k] = heap[0];
heap[0] = A[idx];
adjust_heap(heap, 0, k-1);
++idx;
}
// 對剩下的n-k個數(shù)進行排序
for(int i=k-1; i>=0; i--){
A[idx - k] = heap[0];
++idx;
heap[0] = heap.back();
heap.pop_back();
adjust_heap(heap, 0, heap.size()-1);
}
return A;
}
};
