题目
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。
思路
在所有的排序中，与位置有关的排序是插入排序和堆排序，根据题中所描述，移动的位置不超过K，那么插入排序能达到O（n *** k），堆排序可以达到O（logk * n），最后选择使用大小为k的小顶堆来不断进行处理
答案
void swapInt(int i, int j, int *A) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void adjustMinHeap(int *B, int start, int end) {
for (int current = start, left = current * 2 + 1; left <= end; current = left, left = left * 2 + 1) {
// 获取左右节点中最小的
if (left < end && B[left] > B[left + 1]) {
left++;
}
if (B[current] > B[left]) {
swapInt(current, left, B);
} else {
break;
}
}
}
vector<int> sortElement(vector<int> A, int n, int k) {
// 新建一个辅助排序的数组
int *B = new int[k];
for (int i = 0; i < k; i++) {
B[i] = A[i];
}
// 构造最小堆
for (int i = k/2 - 1; i >= 0; i--) {
adjustMinHeap(B, i, k - 1);
}
// 中间阶段
for (int i = k; i < n; i++) {
A[i - k] = B[0];
B[0] = A[i];
adjustMinHeap(B, 0, k - 1);
}
// 最后阶段
for (int i = n - k; i < n; i++) {
A[i] = B[0];
k--;
B[0] = B[k];
adjustMinHeap(B, 0, k);
}
return A;
}
