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, j-1]了，所以從堆中取出來就是第j個大的。即在數組的第j個位置上。

方法2：

a[i]在排序后的位置是[i-k, i+k]，a[i+2k]在排序后的位置是[i+k, i+3k]，必然有a[i] <= a[i+2k]，所以數組a里實際上有2k個各自有序的、交錯的子序列，如a1=｛a[0], a[2k], a[4k]...｝,a2={a[1], a[2k+1], a[4k+1], ...}?
所以可以用2k-路歸并排序，用一個大小為2k的小頂堆輔助歸并，時間復雜度是O（n*log2k）

總結

以上是生活随笔為你收集整理的优化排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。