题目
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。
测试用例 [2,1,4,3,6,5,8,7,10,9],10,2
返回 [1,2,3,4,5,6,7,8,9,10]
思路
比较直观的一种想法是直接插入排序，每次插入的时间复杂度是O(k)，所以总的时间复杂度是O(n*k)的,空间复杂度是O(1)。
还有一种解法是利用堆排序，维护一个大小为k的小根堆(类比滑动窗口)。在遍历数组的过程中，将根推出并赋值给原数组，在根部插入数组的下一个元素。然后从根部开始下沉,维护堆有序。当窗口到达数组的末尾后，直接进行普通的堆排序，依次推出最小根即可。插入元素并维护堆有序的时间复杂度是O(lgk),总的时间复杂度是O(n*lgk),空间复杂度是O(k)。
代码如下，小根堆是通过下沉排序操作构建的。
import java.util.*;
public class ScaleSort {
public int[] sortElement(int[] A, int n, int k) {
int[] aux = new int[k];
for (int i = 0; i < k; i++) {
aux[i] = A[i];
}
//建立一个小根堆,由aux[]数组组成
for (int i = (k - 2) / 2; i >= 0; i--) {
sink(aux, i, k - 1);
}
//每次取出小根堆的根，换为新的元素，再sink维护小根堆
for (int i = 0; i < n - k; i++) {
A[i] = aux[0];
aux[0] = A[i + k];
sink(aux, 0, k - 1);
}
//将根和尾节点交换，完成堆排序
for (int i = n - k; i < n; i++) {
A[i] = aux[0];
swap(aux, 0, k-1);
k--;
sink(aux, 0, k-1);
}
return A;
}
//下沉排序操作
private void sink(int[] A, int lo, int hi) {
int child;
while ((child = 2 * lo + 1) <= hi) {
if (child < hi && A[child] > A[child + 1]) child++;
if (A[lo] <= A[child]) break;
swap(A, lo, child);
lo = child;
}
}
private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
