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

Question

可能重复:
检查列表是否已排序的Pythonic方法

在python中,如何测试数字列表是否已经排序？

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))

对于具有一百万个条目的随机排序列表,这比其快10000多倍the_list == sorted(the_list).

Answer 2

some_list == sorted(some_list)

Answer 3

通常,您应该已经知道列表是否已排序(因为这是您的输入的定义方式,或者您之前对其进行了排序).

如果您需要验证列表是否已排序,因为如果不是,则要对其进行排序,只需对其进行排序即可.如果列表已经排序,这是一个便宜的操作,并不比明确验证订单贵很多.

换一种说法:

mylist.sort()

现在你知道它已经分类了.

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

因此,在这些极端情况下,排序方法的速度提高了大约三倍,线性方法的速度提高了约20万倍.

注意,这里的真正区别不是 O(n)对O(n log n); 这些复杂性之间的差异并不是那么广泛.主要区别在于线性版本一发现两个乱序值就会短路,其中排序版本总是要完成所有工作.

本机实现可以获得两者的理想性能,提供O(n)复杂性,短路能力以及本机代码的低开销,这使得排序方法更快.如果(并且只有!)性能真的很重要,那将是正确的解决方案.

(请注意,通常我不建议选择基于性能的解决方案,除非性能实际上是一个问题,但是值得注意的是,因为这两种方法都不比另一种方法简单得多.排序版本有点简单易懂,但有关于迭代版本也没什么复杂的.)