百度笔试题：一个已经排序好的很大的数组，现在给它划分成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; } }