已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过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]
思路： 1.本题给定的数组几乎有序，选用基础排序中的插入排序表现也还行 2.比较好的一个解法就是采用堆排序。由于每个元素移动到有序的位置，其移动的距离可以不超过k,故，数组内最小值的下标必定在0~(k-1)这个区间。将这个区间的数据建成堆，堆顶元素即最小值。依次将位置k及后面的元素插入堆中，每插入一个元素后，做堆化调整都能产生一个最小值，然后将最小值放进原数组的相应位置。时间复杂度可达到O(n*logk)。
代码：
import java.util.*; public class ScaleSort { public int[] sortElement(int[] A, int n, int k) { int[] heap = new int[k]; for(int i=0;i<k;++i){ heap[i] = A[i]; } buildheap(heap,k); int pos = 0; for(int i=k;i<n;++i){ //取堆顶元素 放入A中 A[pos++] = heap[0]; //将堆后面的元素插入堆中 heap[0] = A[i]; //调整堆顶元素 adjustheap(heap,0,k); } //进行最后的堆排序 int tail = k; while(tail>0){ A[pos++] = heap[0]; heap[0] = heap[--tail]; adjustheap(heap,0,tail); } return A; } //建堆 private void buildheap(int[] heap, int tail) { for(int i=tail/2;i>=0;--i){ adjustheap(heap,i,tail); } } private void adjustheap(int[] heap, int pos,int tail) { int fpos = pos; int lpos = 2*fpos+1; int rpos = 2*fpos+2; while(lpos<tail){ if(rpos<tail){ int min = heap[lpos]<heap[rpos]?lpos:rpos; if(heap[fpos]>heap[min]){ swap(heap,fpos,min); fpos = min; lpos = fpos*2+1; rpos = fpos*2+2; }else{ return; } }else{ if(heap[fpos]>heap[lpos]){ swap(heap,fpos,lpos); } return; } } } private void swap(int[] heap, int fpos, int lpos) { int tmp = heap[fpos]; heap[fpos] = heap[lpos]; heap[lpos] = tmp; } }