排序几乎排序后的数组（元素放错地方不超过k）的 [英] Sorting an almost sorted array (elements misplaced by no more than k)

问题描述

有人问我这个面试问题最近：

I was asked this interview question recently:

您正在考虑到几乎是排序的数组，在每个 N 元素可以由不多放错位置比 K 的位置。找到一个空间和时间有效的算法来对数组进行排序

You're given an array that is almost sorted, in that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

我有一个 O（N日志K）解决方案如下：

I have an O(N log k) solution as follows.

让我们表示改编[0到n）意味着数组从指数的元素 0 （含），以 N （不包括）。

Let's denote arr[0..n) to mean the elements of the array from index 0 (inclusive) to N (exclusive).

• 排序改编[0..2k）
  • 现在，我们知道，改编[0..k）是他们最后的排序位置...
  • ...但改编[k..2k）仍然可以通过 K ！
  • Sort arr[0..2k)
    • Now we know that arr[0..k) are in their final sorted positions...
    • ...but arr[k..2k) may still be misplaced by k!
    • 现在，我们知道，改编[k..2k）是他们最后的排序位置...
    • ...但改编[2k..3k）仍然可以通过 K错位
    • Now we know that arr[k..2k) are in their final sorted positions...
    • ...but arr[2k..3k) may still be misplaced by k
    • 在这最后一步可能比其他步骤更便宜时，你有小于 2K 左元素

    在每个步骤中，您排序顶多在 0（K数K）2K 元素，把至少 K 在每一步的结束在最终排序位置的元素。有 O（N / K）的步骤，让整体复杂性是 O（N日志K）。

    In each step, you sort at most 2k elements in O(k log k), putting at least k elements in their final sorted positions at the end of each step. There are O(N/k) steps, so the overall complexity is O(N log k).

    我的问题是：

    • 是 O（N日志K）最佳？在这个问题能改善？
    • 您可以做到这一点没有（部分）重新排序相同的元素？
    • Is O(N log k) optimal? Can this be improved upon?
    • Can you do this without (partially) re-sorting the same elements?

    推荐答案

    随着鲍勃·塞奇威克在他的博士论文工作显示（和后续项），插入排序绝对的粉碎的了几乎排序阵。在这种情况下，您的渐近看起来不错，但如果K＆LT; 12我敢打赌，插入排序每次都会获胜。我不知道，有一个很好的解释的为什么的插入排序这样做很好，但看的地方是在塞奇威克的教科书题为一个算法的（他做了许多版本不同的语言）。

    As Bob Sedgewick showed in his dissertation work (and follow-ons), insertion sort absolutely crushes the "almost-sorted array". In this case your asymptotics look good but if k < 12 I bet insertion sort wins every time. I don't know that there's a good explanation for why insertion sort does so well, but the place to look would be in one of Sedgewick's textbooks entitled Algorithms (he has done many editions for different languages).

    • 我不知道○是否（N日志k）是最佳的，但更重要的是，我真的不关心＆mdash;如果k很小，就这么重要的常数因子，如果k是大，你可能也只是对数组进行排序。

    • I have no idea whether O(N log k) is optimal, but more to the point, I don't really care—if k is small, it's the constant factors that matter, and if k is large, you may as well just sort the array.

    插入排序将钉这个问题，而无需重新排序相同的元素。

    Insertion sort will nail this problem without re-sorting the same elements.

    大O符号都是很好的算法类，但在现实世界中，常量关系。这一切都太容易忽视这一点。 （我说这是谁教大O符号教授！）

    Big-O notation is all very well for algorithm class, but in the real world, constants matter. It's all too easy to lose sight of this. (And I say this as a professor who has taught Big-O notation!)

    这篇关于排序几乎排序后的数组（元素放错地方不超过k）的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！