如何检查列表是否已排序？

Question

在Python中，如何测试一个数字列表是否已经排序？

- Uri Laserson

Answer 1

只有通过对列表进行迭代（隐式或显式）才能实现这一点：

all(b >= a for a, b in zip(the_list, the_list[1:])

如果你需要对列表进行排序，为什么不直接对其排序呢？在已经排序的列表上，Python的排序算法会非常便宜，可能比上面的测试还要便宜。

编辑：由于这变成了有关性能的讨论，因此这里提供了一种使用惰性迭代器的版本：

it = iter(the_list)
it.next()
all(b >= a for a, b in itertools.izip(the_list, it))

对于一个随机排序的含有一百万个元素的列表而言，这种方法比the_list == sorted(the_list)要快超过一万倍。

- Sven Marnach

---

实际上，这个测试所需时间大约是排序时间的两倍。但是与排序后测试相比，测试相等性几乎不需要时间，因此 some_list == sorted(some_list) 在任何情况下都是更好的解决方案。 - Lennart Regebro

这比对随机排序的列表进行排序要快得多。如果您使用itertools.izip，尤其是在测试早期短路的情况下，速度会更快。如果您的列表已经按可预测或预排序的顺序排列，则排序将更快，因为Python的排序在这方面很好，而此测试无法短路。当然，如果性能真的很重要（OP没有说过），那么本地模块可以获得两全其美的效果。 - Glenn Maynard

@Glenn，@Lennart：显然这个代码并没有考虑到大列表的性能问题。它使用的额外内存至少是初始列表内存的三倍（在执行zip()期间；请注意，the_list[1：]复制了列表）。为了完整起见，我将添加一个使用惰性迭代器的解决方案。 - Sven Marnach

使用next(it, None)代替it.next()以避免StopIteration异常（空列表是有效输入（始终排序））。微小的挑剔：a <= b更容易阅读（一开始我认为您的代码检查降序是由于>=）。 - jfs

Answer 2

some_list == sorted(some_list)

- Ignacio Vazquez-Abrams

---

这个算法不必要地使用了“O(n log n)” 的时间复杂度，并且没有短路机制。 - Mike Graham

很抱歉，但这不能成为最佳答案。为什么要对整个集合进行排序比较，而不是早期证明某些内容未被排序呢？ - Isaac Nequittepas

Answer 3

通常情况下，您应该已经知道列表是否已排序（因为这是您的输入定义方式，或者您之前已经对其进行了排序）。

如果您需要验证列表是否已排序，因为如果没有排序，您想要对其进行排序，请直接对其进行排序。如果列表已经排序，那么这是一项廉价操作，而且比显式验证顺序的成本稍微高一些。

换句话说：

mylist.sort()

现在你知道它已经排序了。

- Ivo van der Wijk

---

使用某些排序算法，对已经排序的列表进行排序是一项昂贵的操作。但在Timsort中并非如此，但这显然是Python的实现细节。 - Mike Graham

对于某些问题域，知道列表是否已排序也很有用 - 您不一定希望项目已排序，只需知道它们是否已排序即可。一个明显的例子是为排序函数编写单元测试。 :) - fluffy

Answer 4

更多是对其他答案的评论而非回答，但该网站不允许适当的评论。

如果列表已经部分或完全排序，则排序解决方案会更快。 如果列表很可能是随机顺序，或者列表早期顺序混乱，则迭代解决方案会更快。

这是由于两个原因。 首先，当Python获得按其理解的顺序（部分排序，反转等）的数据时，Python的排序非常出色，但是如果数据是随机的或以其他方式不可预测，那么它无法比任何其他排序做得更好。 其次，如果迭代解决方案发现列表无序，则可以快速中断几乎没有工作。

这显示了完全相反的极端：

import timeit, random, itertools

def a(data):
    return all(b >= a for a, b in itertools.izip(data, itertools.islice(data, 1, None)))

def b(data):
    return data == sorted(data)

def main():
    data = range(1000000)
    print "Sorted, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Sorted, sort:", timeit.timeit(lambda: b(data), number=10)

    random.shuffle(data)
    print "Random, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Random, sort:", timeit.timeit(lambda: b(data), number=10)

在我的系统上，这些时间如下：

Sorted, iterative: 1.42838597298
Sorted, sort: 0.498414993286
Random, iterative: 0.000043
Random, sort: 10.5548219681

因此，在这些极端情况下，排序方法大约快三倍，而线性方法大约快两万倍。

请注意，真正的区别在于不是O（n）与O（n log n）; 这些复杂度之间的差距并不那么大。主要区别在于线性版本只要找到两个顺序错误的值就可以立即停止，而排序版本总是必须完成所有工作。

本地实现可以获得两者的理想性能，具有O（n）复杂度、短路的能力以及使排序方法更快的本地代码的低开销。如果（且仅当！）性能确实很重要，那将是正确的解决方案。

（请注意，通常我不会建议根据性能选择解决方案，除非性能确实是一个问题，但这里值得注意的是，两种方法都没有比另一种简单得多。排序版本稍微容易理解一些，但迭代版本也没有任何复杂之处。）

- Glenn Maynard

---

如果性能很重要，那么显式循环 for a, b in izip(data,islice(data, 1, None)):if a > b: return False 比 all() 变体快约50%。 - jfs

Answer 5

if L == (lambda pp=[]: reduce(lambda p, i: pp.append(reduce(lambda t, i:
        (lambda t, i, j: (lambda l=[]: map(lambda x: (lambda xx=l.append(1):
        t[sum(l) - 1] if sum(l) not in map(1..__radd__, (i, j)) else (t[i] if
        sum(l) == j + 1 else t[j]))(), t))())(t, i, i + 1) if t[i] >= t[i + 1]
        else t, xrange(len(p) - 1), p)) or pp[-1], iter(lambda: len(pp) >= 2
        and list.__eq__(*pp[-2:]), True), L))():
    print "yeah, it's sorted"

- habnabit

---

什么？这有什么用？这不是一行代码的比赛。加入一些新行和注释，你的代码将变得更易读，全世界的人都会喜欢它。 - sbartell

@J.F. Sebastian，如果不清楚的话，我的代码对问题中的列表进行了冒泡排序，然后检查结果是否等于原始列表。 - habnabit

保证让那些试图理解其工作原理的人脑残。使用调试器进行意外旅程更有趣！我希望看到小组中其他开发人员在他们可爱的IDE中打开代码，然后看到这个表情：))). 我猜他们会拿着球棒追着这样的代码作者:) - DmitrySemenov

因为这段代码非常难以理解，所以被踩了。Stack Overflow 应该提供尽可能简单的答案。另请参阅 Python 之禅，第四条：“复杂比复杂好”。 - András Aszódi

@user465139 我认为这是复杂的，而不是复杂的。所以，我猜我们同意了？ - habnabit

我所能想到的唯一合理用途就是作为一个典型的反例，告诉大家如何不要写 Python 或者任何编程语言... - rschwieb