百度笔试题：一个已经排序好的很大的数组，现在给它划分成m段，每段长度不定，段长最长为k，然后段内打乱顺序，请设计一个算法对其进行重新排序

import java.util.Arrays;

/**
 * 最早是在陈利人老师的微博看到这道题：
 * #面试题#An array with n elements which is K most sorted，就是每个element的初始位置和它最终的排序后的位置的距离不超过常数K
 * 设计一个排序算法。It should be faster than O(n*lgn)。
 * 
 * 英文原题是：
 * Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. 
 * For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
 * 
 * 微博里面的回复提到这道题的另一个表述：
 * @castomer：回复@华仔陶陶:今年百度校园招聘笔试题目我遇到了一道题和这个基本一样。“
 * 一个已经排序好的很大的数组，现在给它划分成m段，每段长度不定，段长最长为k，然后段内打乱顺序，请设计一个算法对其进行重新排序” 
 * 
 * 两种解法：
 * 1、插入排序，时间复杂度是O(n*k)
 *    由于“K most sorted”，寻找位置时最多只会寻找k位，因此复杂度从最坏情况的O(n*n)下降到O(n*k), 但插入排序没有充分利用“K most sorted”这个条件
 * 2、最小堆
 *    @castomer 认为堆的大小是k
 *    这要看k most sorted怎么理解了
 *    例如，如果对于{4, 3, 2, 1}认为k=3，那么堆的大小就应该是4。因为如果取3的话，第一次最小堆{2, 3, 4}排序后取出最小值2，第二次最小堆排序后取出最小值1，2排在1前面，显然不合理
 *    
 *    最小堆的时间复杂度是O(k) + (n-k) * O(lgk)：
 *    建堆：O(k)，k为堆的大小
 *    堆排序：(n-k) * O(lgk)
 *    
 */
public class KSortedArray {

    public static void main(String[] args) {
        int k = 3;
        int[] array = {2, 6, 3, 12, 56, 8};
        insertSort(array);
        minHeapSort(array, k);
    }
    
    public static void insertSort(int[] arrayToSort) {

        //...略去输入合法性检查
        
        //复制数组，不影响原数组
        int len = arrayToSort.length;
        int[] array = new int[len];
        System.arraycopy(arrayToSort, 0, array, 0, len);
        
        for (int i = 1; i < len; i++) {
            int itemToInsert = array[i];
            while(i > 0 && itemToInsert < array[i - 1]) {
                array[i] = array[i - 1];
                i--;
            }
            array[i] = itemToInsert;
        }
        
        System.out.println(Arrays.toString(array));
    }

    public static void minHeapSort(int[] arrayToSort, int k) {
        
        int len = arrayToSort.length;
        int[] array = new int[len];
        System.arraycopy(arrayToSort, 0, array, 0, len);
        
        int[] sortedArray = new int[len];
        int[] heapValues = new int[k + 1];
        System.arraycopy(array, 0, heapValues, 0, k + 1);
        MinHeap heap = new MinHeap(heapValues);
        
        //将剩下的元素陆续推入堆里，并“吐”出最小值
        int j = 0;
        for (int i = k + 1; i < len; i++) {
            sortedArray[j++] = heap.getRootValue();
            heap.replaceRootValueWith(array[i]);
            heap.reheap();
        }
        
        //没有更多元素进入了，此时剩下k个元素，堆不断收缩，直至为0
        //事实上这个while循环可以并入上面的for循环
        while (j < len) {
            sortedArray[j++] = heap.getRootValue(); 
            heap.minimize();
        }
        
        System.out.println(Arrays.toString(sortedArray));
    }
}


/**
 * 最小堆，只将本次排序中调用到的方法声明为public
 */
class MinHeap {
    
    private int[] values;
    private int lastIndex;
    
    public MinHeap(int[] values) {
        init(values);
    }
    
    public void reheap() {
        reheapCore(0, values.length - 1);
    }
    
    public int getRootValue() {
        return values[0];
    }
    
    public void replaceRootValueWith(int newRootValue) {
        values[0] = newRootValue;
    }
    
    public void minimize() {
        if (lastIndex > 0) {
            this.replaceRootValueWith(values[lastIndex]);
            lastIndex--;
            this.reheapCore(0, lastIndex);
        }
    }
    
    private void init(int[] values) {
        int size = values.length;
        this.lastIndex = size - 1;
        this.values = new int[size];
        System.arraycopy(values, 0, this.values, 0, size);
        int lastIndex = size - 1;
        int lastRootIndex = getRootIndex(lastIndex);
        for (int rootIndex = lastRootIndex; rootIndex >= 0; rootIndex--) {
            reheapCore(rootIndex, lastIndex);
        }
    }
    
    private void reheapCore(int rootIndex, int lastIndex) {
        if (!(isValidIndex(rootIndex) && isValidIndex(lastIndex))) {
            System.out.println("invalid parameters");
            return;
        }
        int orphan = values[rootIndex];
        int leftIndex = getLeftIndex(rootIndex);
        boolean done = false;
        while (!done && leftIndex <= lastIndex) {
            int rightIndex = getRightIndex(rootIndex);
            int smallerIndex = leftIndex;
            if (rightIndex <= lastIndex && values[rightIndex] < values[leftIndex]) {
                smallerIndex = rightIndex;
            } 
            if (values[smallerIndex] < values[rootIndex]) {
                swap(values, smallerIndex, rootIndex);
                rootIndex = smallerIndex;
                leftIndex = getLeftIndex(rootIndex);
            } else {
                done = true;
            }
        }
        values[rootIndex] = orphan;
        //System.out.println(Arrays.toString(values));
    }
    
    private int getLeftIndex(int rootIndex) {
        return rootIndex * 2 + 1;
    }
    
    private int getRightIndex(int rootIndex) {
        return rootIndex * 2 + 2;
    }
    
    private int getRootIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }
    
    private boolean isValidIndex(int index) {
        return index >=0 && index < values.length;
    }
    
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
}