我有一个部分排序的数组，其特点是每个元素都在其正确排序位置的d个单位内。我想知道是否有一种方法可以利用这个特点，在少于n log n的时间内对该数组进行排序。
5个回答
阿里云服务器只需要99元/年，新老用户同享，点击查看详情
9
就我所知...
创建一个大小为2d的“滑动窗口”。
从[0,2d)开始。对窗口中的元素进行排序；现在，0到d-1个元素被保证正确。
将窗口向前滑动d，现在是[d,3d)。对这些元素进行排序，保证了d到2d-1之间的元素是正确的。
再向前滑动d，现在是[2d,4d)。对这些元素进行排序。以此类推。
每次排序都是O(d log d)，需要n/d步才能到达末尾，因此这是O(n/d * d log d) = O(n log d)。如果d是常数，那么就是O(n)。
[编辑]
您在评论中提出了一个很好的观点;我没有证明每个迭代都保留了每个元素都在其正确位置的d个单位的属性。
所以...
引理：如果A是具有每个元素都在其正确位置的d个单位内的属性的数组，并且您对A中的任何连续子序列进行排序以创建数组A'，则A'中的每个元素都在其正确位置的d个单位内。
证明：由于这是关于排序性质（而不是性能）的引理，因此使用哪种算法对我们没有影响。所以使用冒泡排序。找到子序列中任意两个顺序不正确的元素并交换它们。只有三种情况：两个元素都在数组中的正确位置之前；两个元素都在数组中的正确位置之后；或者它们在数组中的正确位置之间。
例如，假设A[i]属于位置i'，A[j]属于位置j'，i＜j，但A[i]＞A[j]。那么i'＞j'（因为这是元素“应该在”的地方，而且A[i]＞A[j]）。情况1：假设i'和j'都大于i和j；也就是说，顺序是i＜j＜j'＜i'。但是根据假设，i'距离i仅有d个单位，因此整个范围最多只有d个单位宽。因此，j也在i'的d个单位内，i也在j'的d个单位内，因此当我们交换A[i]和A[j]时，两个元素仍然在它们应该在的位置附近d个单位内。情况2和情况3的分析类似。
因此，冒泡排序的每个步骤 - 在A的任何子序列上 - 都将保留所需的属性，从而可以得出整个冒泡排序将保留所需的属性，从而可以得出任何排序都将保留所需的属性。证毕。
- Nemo
3
谢谢。所有的答案都很好，但我正在寻找的是O(n log d)的界限。 - Schemer
这个算法是否保持每个元素始终在其正确排序位置的d个单位之内的属性？ - Schemer
@Schemer：这是一个非常好的问题。我已经更新了我的答案。 - Nemo
7
是的，可以在O(nd)时间内进行排序。一种解决方案是对插入排序进行简单修改。我们从头到尾处理输入数组；对于每个元素，我们查看输出数组的最后d个元素，并将新元素插入到其适当的位置。
当然，可能会有更快的算法；选择这种特定的算法是为了更容易地展示渐近界限。
- bdonlan
2
仍然是
O(nd)，但查找范围在 max 0 (i-d) ... min n (i+d) 之间。 - nlucaroni我们不需要查看
i之后的元素，因为我们还没有在那里插入任何元素。如果i应该放在i+d处，它将被稍后插入放置到那里。 - bdonlan4
是的，不管你信不信，冒泡排序可能是部分排序数组中最好的排序算法。当数组完全有序时，其最佳情况的性能为O(n)。
维基百科关于冒泡排序的介绍：http://en.wikipedia.org/wiki/Bubble_sort
编辑：具体来说，是“改进的冒泡排序”，带有一个标志以在已经按顺序排列时跳过交换操作。
- Edgar Velasquez Lim
2
插入排序可能是最好的选择。我将其保留以供参考。还要考虑使用冒泡排序并说它很高效，这太棒了。 - Edgar Velasquez Lim
有没有一个开源实现的地方，针对部分排序数组进行插入损失优化？ - Royi
3
- user541686
1
1Timsort 源自 Python，是一种自适应排序算法。 - Michael J. Barber
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，