在numpy中实现插入排序？

Question

请问在numpy里有没有插入排序的功能？我需要对我的数组进行排序，但是内置的快速排序、归并排序和堆排序对几乎已经排好序的数组不太合适。

Answer 1

可以考虑将 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

Answer 2

来自 numpy 1.17.0 的发布说明：

Timsort 已经被实现，现在取代了 mergesort。[...] Timsort 在已经排序好或者几乎排序好的数据上表现更好，而在随机数据上表现和 mergesort 差不多。

到目前为止，NumPy 1.17.0 还没有发布，但等它发布后，你可以通过在 sort 调用中指定 kind='stable' 或 kind='mergesort' 来选择 Timsort：

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

这样可以满足你想用插入排序处理“几乎排序好的数据”的需求，同时也能利用输入数据的其他顺序，并且在最坏情况下比插入排序表现得好得多。

早期的 numpy 版本 没有针对几乎排序好的数据的快速方法。