c++ - 对一些数字已经排序的数组进行部分排序

Question

我必须按降序对数组进行部分排序，其中一些数字可能已经排序。

他们是否有任何可以有效地完成它的功能或任何有效的算法。

Answer 1

Timsort专为这种情况而设计。

Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently.

另一种选择是 Smoothsort ，也旨在利用部分排序的数据。

It is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O(n log n). The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state.