сортировка вставки в numy?

Question

Есть ли где-нибудь в numpy сортировка вставок? Мне требуется argsort для моего массива, но встроенный быстрый, объединение и куча не подходят для почти отсортированного массива.

Answer 1

Из примечаний к выпуску numpy 1.17.0 :

Timsort был реализован и теперь используется вместо сортировки слиянием.[...] Timsort обладает улучшенной производительностью для уже или почти отсортированных данных и работает как сортировка слиянием для случайных данных.

На момент написания этой статьи NumPy 1.17.0 еще не вышел, нокогда это произойдет, вы сможете выбрать Timsort, указав kind='stable' или kind='mergesort' в вызове sort:

sorted = numpy.sort(unsorted, kind='stable')

Это удовлетворяет желаемой роли "быстрое на почти отсортированных данных".использовать сортировку вставки для, в то же время используя преимущества другого порядка во входных данных и имея намного лучшее поведение при наихудшем случае, чем сортировка вставкой.

Более ранние версии numpy не имеют быстрого метода для почти отсортированных данных.

Answer 2

Как насчет использования numpy.searchsorted в сочетании с numpy.insert:

http://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html

http://docs.scipy.org/doc/numpy/reference/generated/numpy.insert.html