http://www.cnblogs.com/jack204/archive/2012/10/10/2717795.html
已知一个n个元素的数组,第i个元素在排序后的位置在[i-k,i+k]区间,k<<n .让你设计一个算法对数组排序,要求时间复杂度最小
方法1:
建一个k的小堆,每次取最小,插入下一个,维护这个堆n次,总共为O(nlogk)。
归纳法证明:
1 前k个取出最小的必然就是全部数组的最小的,因为第一个位置的在[0, k-1]之中的一个。
2 第j个取出来的数字,在数组就在j的位置上。因为根据题意,第j个大的必然在(j-k, j+k)之间。他必然在[0, j+k-1]中第j个大的,前面已经有[0, ......
阅读全文