如何快速判断一个数组是否已排序？

Question

这可能看起来像是Pandas中检查非索引列是否排序的重复问题。

我阅读了那篇文章和所有答案。除了一个答案之外，没有人涉及使用numpy。它全部都集中在Python列表上。通过使用numpy标签提出类似的问题，我相信我会得到不同类型的答案。话虽如此，接下来是问题。

考虑两个数组a和b。b已排序，而a未排序。

a = np.array([2, 1, 3, 0])

b = np.arange(4)

我已经编写了这个函数来确定排序性。

def is_sorted(x):
    return (np.arange(len(x)) == np.argsort(x)).all()

除此之外，我还能做些什么来改进这个想法？有没有最快的 pandas 或者 numpy 算法可以判断一个 pd.Series 或者 np.ndarray 是否已经排序？

---

is_sorted(a)

False  

---

is_sorted(b)

True  

---

- piRSquared

---

这里提到了一些Pandas算法，链接为：https://dev59.com/5F4c5IYBdhLWcg3wAWPv。我不是在说这是一个重复的问题，只是看起来有一些好的建议。 - JohnE

“(np.diff(a)>0).all()”和“(np.diff(b)>0).all()”是什么意思？唯一的问题在于反向排序。但是我认为“np.abs(np.diff(a)>0).all()”应该没问题吧？ - Abdou

大多数临时解决方案在数据中存在NaN时会失败。pd.algos.is_lexsorted()在这种情况下不会失败。 - John Zwinck

我认为这不是重复的，因为在所谓的重复中并没有涉及到性能方面（最快的方式）。 - MSeifert

pandas.algos.is_lexsorted 实际上假定输入为 64 位有符号整数。由于 IEEE 浮点数的工作方式，这意味着它恰好可以处理 64 位 NaN，但在负浮点数输入时会失败。这不是解决方案。 - user2357112

Answer 1

一个数组排序的时间复杂度是O(nlogn)，但是判断一个数组是否已经排好序只需要O(n)。

is_sorted = lambda x: (np.diff(x)>=0).all()

- Da Qi

---

感谢添加大O复杂度信息！ - piRSquared

如果存在NaN值，则此操作将失败。 - John Zwinck

你只需要分成两步：1）数组是否可排序？2）如果是，它是否已排序？ - Da Qi

在查看了pd.algos.is_lexsorted之后，我很满意这是一个重复的问题。is_lexsorted非常快。 - piRSquared