对几乎排序的数组进行排序(错误放置的元素不超过k)

Question

对几乎排序的数组进行排序(错误放置的元素不超过k)

pol*_*nts 65 arrays sorting algorithm

我最近被问到这个面试问题:

您将获得一个几乎已排序的数组,因为每个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)可能仍然被错放了k
分类 arr[2k..4k)
....
直到你排序arr[ik..N),然后你就完成了!
- 如果2k剩下的元素少于其他元素,那么最后一步可能比其他步骤便宜

在每个步骤中,您对大多数2k元素进行排序,在每个步骤O(k log k)结束时将至少k元素放在最终排序位置.有O(N/k)步骤,所以整体复杂性O(N log k).

我的问题是:

是O(N log k)最佳的？这可以改进吗？
你可以在没有(部分)重新排序相同元素的情况下做到这一点吗？

Answer 1

Nor*_*sey 36

正如Bob Sedgewick在他的论文工作(和后续工作)中所表明的那样,插入排序绝对会破坏 "几乎排序的数组".在这种情况下,你的渐近线看起来不错,但如果k <12,我认为插入排序每次都会获胜.我不知道为什么插入排序这么好有一个很好的解释,但是看看的地方将是Sedgewick的一本名为算法的教科书(他为不同的语言做了很多版本).

我不知道O(N log k)是否是最优的,但更重要的是,我并不在乎 - 如果k很小,它是重要的常数因子,如果k很大,你可能也只是对数组进行排序.
插入排序将解决此问题,而无需重新排序相同的元素.

Big-O表示法对于算法类来说非常好,但在现实世界中,常量很重要.很容易忽视这一点.(我说这是一位教过Big-O符号的教授!)

你能解释一下他说的更多内容而不仅仅是链接吗？答案中的参考文献非常棒,但是stackoverflow本身的实质内容甚至是令人敬畏的! (6认同)
好吧,即使在现实世界中,当输入大小变得足够大时,渐近线比常数更重要.:-)插入排序有一个非常好的常数,但O(n log k)渐近优于O(nk)*的事实可能*很重要 - 例如,如果k增大,那么k≈≈n会变大？(这也取决于面试官正在寻找什么.:p) (5认同)
虽然SO是一个编程站点,但我认为问题仍然值得正确回答.例如,我们不应该说所有算法都是O(1),即使在编程中遇到的所有运行时间都是以常数为界(例如10 ^ 1000).更重要的是,*无论*插入排序的常数,有一些足够大的k,之后插入排序不再更快,我们不能"不如"对整个数组进行排序.(我真的怀疑,即使有一万亿个元素(k = 40),插入排序是否更快.) (5认同)
@Norman:也许你真的可以指出那些对几乎排序的数组有所主张的论文/书籍章节？只是链接到主页几乎没用.另外,如果k = sqrt(n),只是说插入排序会使它无效.我真的不明白为什么这个答案有这么多的选票. (4认同)
@Moron:如果k = log n则k很小.一百万的日志基数只有20个.@Everyone:SO是一个*编程*网站,而不是*CS理论*网站! (3认同)
我忍不住注意到Bubble Sort也会有O(nk)的复杂性.它不是经常被引用:) (2认同)

Answer 2

小智 19

如果仅使用比较模型,则O(n log k)是最佳的.考虑k = n时的情况.

要回答你的另一个问题,是的,可以通过使用堆来进行排序而不进行排序.

使用2k元素的最小堆.首先插入2k元素,然后删除min,插入下一个元素等.

这保证了O(n log k)时间和O(k)空间,而堆通常具有足够小的隐藏常数.

@polygenelubricants:您可以就地执行此操作.从远端开始,使用max-heap而不是min-heap.将最后一块2k元素就地堆积起来.将第一个提取的元素存储在变量中; 后续元素进入最后一个2k块之前腾出的位置(包含堆结构),类似于常规的堆.当只剩下一个块时,将其固定到位.需要最后的O(n)传递来将最终块"旋转"回初始块.旋转不是微不足道的,但可以在O(n)和O(1)空间中完成. (2认同)
@j_random_hacker你能解释为什么堆必须大小为2k吗？在我做过的例子中,k + 1足够大了. (2认同)

Answer 3

Iva*_*kov 8

已经指出,其中一个渐近最优解决方案使用最小堆,我只是想用Java提供代码:

public void sortNearlySorted(int[] nums, int k) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int i = 0; i < k; i++) {
    minHeap.add(nums[i]);
  }

  for (int i = 0; i < nums.length; i++) {
    if (i + k < nums.length) {
      minHeap.add(nums[i + k]);
    }
    nums[i] = minHeap.remove();
  }
}

Run Code Online (Sandbox Code Playgroud)

尽可能添加评论。轻松理解代码是一种好习惯。 (2认同)

Answer 4

Jer*_*fin 7

由于k显然应该是非常小的,插入排序可能是最明显和普遍接受的算法.

在随机元素的插入排序中,您必须扫描N个元素,并且必须将每个元素平均移动N/2个位置,从而总共运算~N*N/2.在大O(或类似)表征中忽略"/ 2"常数,给出O(N ²)复杂度.

在您提议的情况下,预期的操作次数为~N*K/2 - 但由于k是常数,因此k/2在大O特征中忽略整个项,因此总体复杂度为O(N).

`k`不保证是常数,所以这实际上是'O(Nk)`.但是,如果`k`是常数,那么你就是'O(N)`. (2认同)

Answer 5

Rex*_*err 7

如果k足够大,你的解决方案是好的.在时间复杂性方面没有更好的解决方案; 每个元素可能都k不合适,这意味着您需要学习log2 k一些信息才能正确放置,这意味着您log2 k至少需要进行比较 - 所以它至少应该是复杂的O(N log k).

然而,正如其他人所指出的那样,如果k规模很小,那么常数条款就会杀了你.在这种情况下,使用每次操作非常快的东西,比如插入排序.

如果你真的想要达到最佳状态,你可以实现两种方法,并根据它们从一种方法切换到另一种方法k.

归档时间：	15 年，4 月前
查看次数：	26603 次
最近记录：	8 年，7 月前