python - Numpy argsort 不稳定性

Question

最近，我一直在试验 np.argsort，我发现了一些奇怪的东西。

如果你运行下面的代码，你会得到结果:

In [0]: np.argsort([3]*16)
Out[0]:
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
      dtype=int64)

但如果你只做一点点改变:

In [1]: np.argsort([3]*17)
Out[1]:
array([ 0, 14, 13, 12, 11, 10,  9, 15,  8,  6,  5,  4,  3,  2,  1,  7, 16],
      dtype=int64)

我知道 numpy argsort 的默认方法是 quicksort，这是一种不稳定的排序算法。但是，对于上述差异行为有合理的解释吗？这与快速排序的枢轴选择有关吗？如果是，为什么？

Answer 1

我可能错了，因为我没有深入研究它，但 numpy 似乎使用了一种 introsort 混合算法，求助于插入排序(这是稳定的) 对于小范围。

猜猜看 code应该给你一个更好的洞察力。查看代码可以遵循的不同路径，SMALL_QUICKSORT 应该是您正在寻找的神奇数字。