我必须按降序对数组进行部分排序，其中一些数字可能已经排序。
他们是可以有效地做到这一点的任何功能还是任何有效的算法。
问问题
221 次
3 回答
7
Timsort是专门为这种情况设计的。
Timsort 是一种混合排序算法，源自合并排序和插入排序，旨在在多种现实世界数据上表现良好。它是由 Tim Peters 于 2002 年发明的，用于 Python 编程语言。该算法找到已经排序的数据子集，并使用这些子集更有效地对数据进行排序。
另一种选择是Smoothsort，它也被设计为利用部分排序的数据。
它是由 Edsger Dijkstra 在 1981 年开发的 heapsort 的变体。与 heapsort 一样，smoothsort 的上限是 O( n log n )。平滑排序的优点是，如果输入已经排序到某种程度，它会更接近 O( n ) 时间，而无论初始排序状态如何，堆排序平均 O( nlogn )。
于 2012-07-03T12:34:17.607 回答
0
如果您在循环内进行排序，请考虑使用 treap 或红黑树。Treaps 平均速度快（但标准差较大），红黑树的操作时间可变性低（平均操作时间不如，但操作时间标准差低）。IOW，对于批处理应用程序使用treap，对于交互式应用程序，您可能需要一个红黑树，这样您的用户就不必偶尔等待很长时间。
如果你不是在循环中排序，那么 Timsort。
于 2012-07-03T16:43:14.580 回答
0
std::sort一般来说。
尽管确切的实现细节是实现的质量，但良好的实现std::sort应该利用数据的部分排序特性。libc++例如，确实如此。
请注意，如果您知道排序的部分在哪里，您可以使用std::inplace_merge. 例如，假设这v是一个vector[1, 7) 被排序并且 [7, 10) 也被排序的，那么你可以使用std::inplace_merge(v.begin() + 1, v.begin() + 7, v.begin() + 10)但是这更容易出错。
至于结果的顺序：如果<不适合您，请随时提供您自己的比较功能。
于 2012-07-03T13:56:05.490 回答