部分排序一个已经有一些数字排序的数组

Question

我需要对一个数组进行部分降序排序，其中一些数字可能已经排序。

是否有任何能够高效完成此任务的函数或算法。

- user1484638

---

插入排序在数字部分排序时非常理想。 - st0le

Answer 1

Timsort是专门为此情况设计的排序算法。

Timsort是一种混合排序算法，源于归并排序和插入排序，旨在高效地处理各种真实世界的数据。它是由Tim Peters于2002年发明，用于Python编程语言中。该算法找到已经排序的数据子集，并使用这些子集更有效地对数据进行排序。

另一个选择是Smoothsort，也专门设计用于利用部分排序的数据。

这是Edsger Dijkstra在1981年开发的堆排序的变体。与堆排序一样，smoothsort的上限是O（n log n）。 smoothsort的优点在于，如果输入已经在某种程度上排序，则接近O（n）时间，而堆排序无论初始排序状态如何，平均需要O（n log n）。

- vartec

Answer 2

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)，但这更容易出错。

至于结果的顺序：如果 < 不适合您，可以自己提供比较函数。

- Matthieu M.

Answer 3

如果你在循环中进行排序，请考虑使用Treap或红黑树。Treap平均速度快（但标准差较大），红黑树操作时间变化小（平均操作时间不如Treap，但操作时间标准差低）。也就是说，对于批处理应用程序，请使用Treap；对于交互式应用程序，您可能需要使用红黑树，以便用户偶尔不必等待太长时间。

如果您不在循环中进行排序，则使用Timsort。

- user1277476