11 小范围排序

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过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]

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];          
        }
//      SortUtils.printArray(heap);
      build_heap(heap, k);
//      SortUtils.printArray(heap);
      for(int i=0;i<n;i++){
         A[i]=heap[0];
        if(i+k<n){
//           
             heap[0]=A[i+k];
             heap_adjust(heap, 0,k);
        }else{
          heap[0]=heap[n-1-i];   //此处有点绕
          heap_adjust(heap, 0,n-1-i);
        }         
        }
      return A;
      }
    //建立小根堆
    public void build_heap(int[] A,int n) {

          for( int i=n/2-1;i>=0;i--)    //非叶节点最大序号值为n/2 -1
          {
              heap_adjust(A,i,n);    
          }    
  }
    /*
       * 小根堆调整
       * 一次堆调整的平均时间成本为log n
       */
      public void heap_adjust(int[] A,int i,int n){
        int leftChild=2*i+1;    //左孩子的下标
        int rightChild=2*i+2;    //右孩子的下标
        int min=i;                     //min记录较大节点的下标
        if(i<n/2){                       //满足此条件节点才不是叶子节点
          if(leftChild<n&&A[leftChild]<A[min]){
            min=leftChild;
          }
          if(rightChild<n&&A[rightChild]<A[min]){
            min=rightChild;
          }
          if(i!=min){
            int temp=A[i];        //交换A[i]和A[max]
            A[i]=A[min];
            A[min]=temp;

            heap_adjust(A, min, n); //再继续调整子树
          }
        }

      }
}