我最近被问到这个面试问题:
您将获得一个几乎已排序的数组,因为每个
N元素可能被错放的k位置不超过正确排序顺序的位置.找到一种节省空间和时间的算法来对数组进行排序.
我有一个O(N log k)解决方案如下.
让我们表示arr[0..n)从索引0(包括)到N(不包括)的数组元素.
arr[0..2k)
arr[0..k)它们处于最终的排序位置......arr[k..2k)可能仍然被错放了k!arr[k..3k)
arr[k..2k)它们处于最终的排序位置......arr[2k..3k)可能仍然被错放了karr[2k..4k)arr[ik..N),然后你就完成了!
2k剩下的元素少于其他元素,那么最后一步可能比其他步骤便宜在每个步骤中,您对大多数2k元素进行排序,在每个步骤O(k log k)结束时将至少k元素放在最终排序位置.有O(N/k)步骤,所以整体复杂性O(N log k).
我的问题是:
O(N log k)最佳的？这可以改进吗？