用python方法检查列表是否已排序。

Is there a pythonic way to check if a list is already sorted in ASC or DESC

是否有一个python的方法来检查列表是否已经在ASC或DESC中进行了排序?

listtimestamps = [1, 2, 3, 5, 6, 7]

something like isttimestamps.isSorted() that returns True or False.

返回True或False的isttimestamps. is排序()。

I want to input a list of timestamps for some messages and check if the the transactions appeared in the correct order.

我想输入一些消息的时间戳列表，并检查这些事务是否以正确的顺序出现。

17 个解决方案

#1

Actually we are not giving the answer anijhaw is looking for. Here is the one liner:

实际上，我们并没有给出anijhaw正在寻找的答案。这是一行:

all(l[i] <= l[i+1] for i in xrange(len(l)-1))

For Python 3:

Python 3:

all(l[i] <= l[i+1] for i in range(len(l)-1))

#2

I would just use

我只会用

if sorted(lst) == lst:
    # code here

unless it's a very big list in which case you might want to create a custom function.

除非它是一个非常大的列表，在这种情况下，你可能想要创建一个自定义函数。

if you are just going to sort it if it's not sorted, then forget the check and sort it.

如果你只是对它进行排序，如果它没有排序，那么忘记检查并排序它。

lst.sort()

and don't think about it too much.

不要想太多。

if you want a custom function, you can do something like

如果您想要一个自定义函数，您可以做一些类似的事情。

def is_sorted(lst, key=lambda x: x):
    for i, el in enumerate(lst[1:]):
        if key(el) < key(lst[i]): # i is the index of the previous element
            return False
    return True

This will be O(n) if the list is already sorted though (and O(n) in a for loop at that!) so, unless you expect it to be not sorted (and fairly random) most of the time, I would, again, just sort the list.

这将是O(n)，如果列表已经被排序了(和O(n)在一个for循环中)，所以，除非您期望它在大多数情况下没有被排序(和相当随机)，我将再次对列表进行排序。

#3

This iterator form is 10-15% faster than using integer indexing:

这个迭代器表单比使用整数索引快10-15%:

# from itertools import izip as zip # python 2 only!

def is_sorted(l):
    return all(a <= b for a, b in zip(l[:-1], l[1:]))

#4

A beautiful way to implement this is to use the imap function from itertools:

实现这一点的一个很好的方法是使用itertools中的imap函数:

from itertools import imap, tee
import operator

def is_sorted(iterable, compare=operator.le):
  a, b = tee(iterable)
  next(b, None)
  return all(imap(compare, a, b))

This implementation is fast and works on any iterables.

这个实现是快速的，并且适用于任何迭代。

#5

I'd do this (stealing from a lot of answers here [Aaron Sterling, Wai Yip Tung, sorta from Paul McGuire] and mostly Armin Ronacher):

我会这么做(从很多答案中偷取[Aaron Sterling, Wai Yip Tung, sorta from Paul McGuire]，主要是Armin Ronacher):

from itertools import tee, izip

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def is_sorted(iterable, key=lambda a, b: a <= b):
    return all(key(a, b) for a, b in pairwise(iterable))

One nice thing: you don't have to realize the second iterable for the series (unlike with a list slice).

一件好事:您不必实现这个系列的第二个迭代(不像列表切片)。

#6

I ran a benchmark and sorted(lst, reverse=True) == lst was the fastest for long lists, and all(l[i] >= l[i+1] for i in xrange(len(l)-1)) was the fastest for short lists . These benchmarks were run on a MacBook Pro 2010 13" (Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5).

我运行了一个基准并排序(lst, reverse=True) == lst是长列表中最快的，并且所有(l[I] >= l[I +1]在xrange中(len(l)-1))是短列表中最快的。这些基准是在2010年的MacBook Pro笔记本电脑上运行的。

UPDATE: I revised the script so that you can run it directly on your own system. The previous version had bugs. Also, I have added both sorted and unsorted inputs.

更新:我修改了脚本，以便您可以直接在自己的系统上运行它。之前的版本有bug。此外，我还添加了已排序的和未排序的输入。

• Best for short sorted lists: all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 最佳的短排序列表:所有(l[i] >= l[i+1])，在xrange(len(l)-1))
• Best for long sorted lists: sorted(l, reverse=True) == l
• 最好的长排序列表:排序(l，反向=True) == l。
• Best for short unsorted lists: all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 最佳的未排序列表:所有(l[i] >= l[i+1])，在xrange(len(l)-1))
• Best for long unsorted lists: all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 最好的长未排序列表:all(l[i] >= l[i+1])， i在xrange(len(l)-1))

So in most cases there is a clear winner.

所以在大多数情况下，有一个明确的赢家。

UPDATE: aaronsterling's answers (#6 and #7) are actually the fastest in all cases. #7 is the fastest because it doesn't have a layer of indirection to lookup the key.

更新:aaronsterling的答案(#6和#7)实际上是所有案例中最快的。#7是最快的，因为它没有一个间接层来查找键。

#!/usr/bin/env python

import itertools
import time

def benchmark(f, *args):
    t1 = time.time()
    for i in xrange(1000000):
        f(*args)
    t2 = time.time()
    return t2-t1

L1 = range(4, 0, -1)
L2 = range(100, 0, -1)
L3 = range(0, 4)
L4 = range(0, 100)

# 1.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(l[i],l[i+1]) for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 2.47253704071
print benchmark(isNonIncreasing, L2) # 34.5398209095
print benchmark(isNonIncreasing, L3) # 2.1916718483
print benchmark(isNonIncreasing, L4) # 2.19576501846

# 2.
def isNonIncreasing(l):
    return all(l[i] >= l[i+1] for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 1.86919999123
print benchmark(isNonIncreasing, L2) # 21.8603689671
print benchmark(isNonIncreasing, L3) # 1.95684289932
print benchmark(isNonIncreasing, L4) # 1.95272517204

# 3.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(a,b) for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.65468883514
print benchmark(isNonIncreasing, L2) # 29.7504849434
print benchmark(isNonIncreasing, L3) # 2.78062295914
print benchmark(isNonIncreasing, L4) # 3.73436689377

# 4.
def isNonIncreasing(l):
    return all(a >= b for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.06947803497
print benchmark(isNonIncreasing, L2) # 15.6351969242
print benchmark(isNonIncreasing, L3) # 2.45671010017
print benchmark(isNonIncreasing, L4) # 3.48461818695

# 5.
def isNonIncreasing(l):
    return sorted(l, reverse=True) == l
print benchmark(isNonIncreasing, L1) # 2.01579380035
print benchmark(isNonIncreasing, L2) # 5.44593787193
print benchmark(isNonIncreasing, L3) # 2.01813793182
print benchmark(isNonIncreasing, L4) # 4.97615599632

# 6.
def isNonIncreasing(l, key=lambda x, y: x >= y): 
    for i, el in enumerate(l[1:]):
        if key(el, l[i-1]):
            return False
    return True
print benchmark(isNonIncreasing, L1) # 1.06842684746
print benchmark(isNonIncreasing, L2) # 1.67291283607
print benchmark(isNonIncreasing, L3) # 1.39491200447
print benchmark(isNonIncreasing, L4) # 1.80557894707

# 7.
def isNonIncreasing(l):
    for i, el in enumerate(l[1:]):
        if el >= l[i-1]:
            return False
    return True
print benchmark(isNonIncreasing, L1) # 0.883186101913
print benchmark(isNonIncreasing, L2) # 1.42852401733
print benchmark(isNonIncreasing, L3) # 1.09229516983
print benchmark(isNonIncreasing, L4) # 1.59502696991

#7

Although I don't think there is a guarantee for that the sorted built-in calls its cmp function with i+1, i, it does seem to do so for CPython.

虽然我不认为有一个保证，它的cmp函数与I +1的cmp函数是一致的，但是对于CPython来说，它确实是这样做的。

So you could do something like:

你可以这样做:

def my_cmp(x, y):
   cmpval = cmp(x, y)
   if cmpval < 0:
      raise ValueError
   return cmpval

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except ValueError:
      return False

print is_sorted([1,2,3,5,6,7])
print is_sorted([1,2,5,3,6,7])

Or this way (without if statements -> EAFP gone wrong? ;-) ):

或者这样(如果没有的话，> EAFP哪里出错了?);-)):

def my_cmp(x, y):
   assert(x >= y)
   return -1

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except AssertionError:
      return False

#8

Not very Pythonic at all, but we need at least one reduce() answer, right?

不是很复杂，但是我们至少需要一个reduce()答案，对吧?

def is_sorted(iterable):
    prev_or_inf = lambda prev, i: i if prev <= i else float('inf')
    return reduce(prev_or_inf, iterable, float('-inf')) < float('inf')

The accumulator variable simply stores that last-checked value, and if any value is smaller than the previous value, the accumulator is set to infinity (and thus will still be infinity at the end, since the 'previous value' will always be bigger than the current one).

累加器变量只存储最后检查的值，如果任何值小于先前的值，则累加器将被设置为无穷大(因此，在最后将仍然是无穷大，因为“前值”总是大于当前值)。

#9

I use this one-liner based on numpy.diff():

根据numpy.diff():

def issorted(x):
    """Check if x is sorted"""
    return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0?

I haven't really timed it against any other method, but I assume it's faster than any pure Python method, especially for large n, since the loop in numpy.diff (probably) runs directly in C (n-1 subtractions followed by n-1 comparisons).

我并没有对任何其他方法进行计时，但是我认为它比任何纯Python方法都要快，特别是对于大n，因为这个循环在numpy中。diff(很可能)是直接用C (n-1减去，然后是n-1比较)。

However, you need to be careful if x is an unsigned int, which might cause silent integer underflow in numpy.diff(), resulting in a false positive. Here's a modified version:

但是，如果x是未签名的int，则需要小心，因为它可能导致numpy.diff()中的静默整数不足，从而导致错误的正数。这里有一个修改版:

def issorted(x):
    """Check if x is sorted"""
    try:
        if x.dtype.kind == 'u':
            # x is unsigned int array, risk of int underflow in np.diff
            x = numpy.int64(x)
    except AttributeError:
        pass # no dtype, not an array
    return (numpy.diff(x) >= 0).all()

#10

This is similar to the top answer, but I like it better because it avoids explicit indexing. Assuming your list has the name lst, you can generate
(item, next_item) tuples from your list with zip:

这与顶部的答案类似，但我更喜欢它，因为它避免了显式索引。假设您的列表有“lst”的名称，您可以使用zip来从列表中生成(item, next_item) tuple:

all(x <= y for x,y in zip(lst, lst[1:]))

In Python 3, zip already returns a generator, in Python 2 you can use itertools.izip for better memory efficiency.

在Python 3中，zip已经返回了一个生成器，在Python 2中，您可以使用itertools。提高内存效率。

Small demo:

小的演示:

>>> lst = [1, 2, 3, 4]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 4)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
True
>>> 
>>> lst = [1, 2, 3, 2]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 2)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
False

The last one fails when the tuple (3, 2) is evaluated.

当计算元组(3,2)时，最后一个失败。

Bonus: checking finite (!) generators which cannot be indexed:

奖励:检查不能被索引的有限(!)生成器:

>>> def gen1():
...     yield 1
...     yield 2
...     yield 3
...     yield 4
...     
>>> def gen2():
...     yield 1
...     yield 2
...     yield 4
...     yield 3
... 
>>> g1_1 = gen1()
>>> g1_2 = gen1()
>>> next(g1_2)
1
>>> all(x <= y for x,y in zip(g1_1, g1_2))
True
>>>
>>> g2_1 = gen2()
>>> g2_2 = gen2()
>>> next(g2_2)
1
>>> all(x <= y for x,y in zip(g2_1, g2_2))
False

Make sure to use itertools.izip here if you are using Python 2, otherwise you would defeat the purpose of not having to create lists from the generators.

确保使用itertools。如果您使用的是Python 2，则在这里使用izip，否则您将无法创建从生成器中创建列表的目的。

#11

SapphireSun is quite right. You can just use lst.sort(). Python's sort implementation (TimSort) check if the list is already sorted. If so sort() will completed in linear time. Sounds like a Pythonic way to ensure a list is sorted ;)

SapphireSun是相当正确的。您可以使用lst.sort()。Python的排序实现(TimSort)检查列表是否已经排序。如果这样排序()将在线性时间内完成。这听起来像一个python的方法来确保列表是有序的;

#12

As noted by @aaronsterling the following solution is the shortest and seems fastest when the array is sorted and not too small: def is_sorted(lst): return (sorted(lst) == lst)

正如@aaronsterling所指出的，下面的解决方案是最短的，并且在数组排序时看起来是最快的，而不是太小:def is_sort (lst): return(排序(lst) == lst)

If most of the time the array is not sorted, it would be desirable to use a solution that does not scan the entire array and returns False as soon as an unsorted prefix is discovered. Following is the fastest solution I could find, it is not particularly elegant:

如果大多数时间数组没有排序，那么最好使用一个不扫描整个数组并在未排序的前缀被发现的情况下返回False的解决方案。以下是我能找到的最快的解决方案，它不是特别优雅:

def is_sorted(lst):
    it = iter(lst)
    try:
        prev = it.next()
    except StopIteration:
        return True
    for x in it:
        if prev > x:
            return False
        prev = x
    return True

Using Nathan Farrington's benchmark, this achieves better runtime than using sorted(lst) in all cases except when running on the large sorted list.

使用Nathan Farrington的基准测试，在所有情况下，除了在大型排序列表上运行之外，这将比在所有情况下使用排序(lst)更好。

Here are the benchmark results on my computer.

这是我的电脑的基准测试结果。

sorted(lst)==lst solution

排序(lst)= = lst的解决方案

• L1: 1.23838591576
• L1:1.23838591576
• L2: 4.19063091278
• L2:4.19063091278
• L3: 1.17996287346
• L3:1.17996287346
• L4: 4.68399500847
• L4:4.68399500847

Second solution:

第二个解决方案:

• L1: 0.81095790863
• L1:0.81095790863
• L2: 0.802397012711
• L2:0.802397012711
• L3: 1.06135106087
• L3:1.06135106087
• L4: 8.82761001587
• L4:8.82761001587

#13

Lazy

def is_sorted(l):
    l2 = iter(l)
    next(l2, None)
    return all(a <= b for a, b in zip(l, l2))

#14

If you want the fastest way for numpy arrays, use numba, which if you use conda should be already installed

如果您想要最快捷的方法来使用numpy数组，请使用numba，如果您使用conda，那么应该已经安装了它。

The code will be fast because it will be compiled by numba

代码将会很快，因为它将由numba编译。

import numba
@numba.jit
def issorted(vec, ascending=True):
    if len(vec) < 2:
        return True
    if ascending:
        for i in range(1, len(vec)):
            if vec[i-1] > vec[i]:
                return False
        return True
    else:
        for i in range(1, len(vec)):
            if vec[i-1] < vec[i]:
                return False
        return True

and then:

然后:

>>> issorted(array([4,9,100]))
>>> True

#15

Just to add another way (even if it requires an additional module): iteration_utilities.all_monotone:

只需添加另一种方法(即使它需要一个附加模块):iteration_use . all_单调:

>>> from iteration_utilities import all_monotone
>>> listtimestamps = [1, 2, 3, 5, 6, 7]
>>> all_monotone(listtimestamps)
True

>>> all_monotone([1,2,1])
False

To check for DESC order:

检查DESC订单:

>>> all_monotone(listtimestamps, decreasing=True)
False

>>> all_monotone([3,2,1], decreasing=True)
True

There is also a strict parameter if you need to check for strictly (if successive elements should not be equal) monotonic sequences.

如果需要严格检查(如果连续的元素不应该相等)，那么还有一个严格的参数。

It's not a problem in your case but if your sequences contains nan values then some methods will fail, for example with sorted:

在你的例子中这不是问题，但是如果你的序列包含nan值，那么一些方法会失败，例如排序:

def is_sorted_using_sorted(iterable):
    return sorted(iterable) == iterable

>>> is_sorted_using_sorted([3, float('nan'), 1])  # definetly False, right?
True

>>> all_monotone([3, float('nan'), 1])
False

Note that iteration_utilities.all_monotone performs faster compared to the other solutions mentioned here especially for unsorted inputs (see benchmark).

注意,iteration_utilities。与这里提到的其他解决方案相比，all_单调执行得更快，特别是对于未排序的输入(参见基准)。

#16

This is in fact the shortest way to do it using recursion:

if it's Sorted will print True else will print out False

如果它被分类，将打印真实的否则将打印错误。

 def is_Sorted(lst):
    if len(lst) == 1:
       return True
    return lst[0] <= lst[1] and is_Sorted(lst[1:])

 any_list = [1,2,3,4]
 print is_Sorted(any_list)

#17

Definitely works in Python 3 and above for integers or strings:

对于整数或字符串，肯定在python3和上面工作:

def tail(t):
    return t[:]

letters = ['a', 'b', 'c', 'd', 'e']
rest = tail(letters)
rest.sort()
if letters == rest:
    print ('Given list is SORTED.')
else:
    print ('List NOT Sorted.')

=====================================================================

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Another way of finding if the given list is sorted or not

另一种查找给定列表是否排序的方法。

trees1 = list ([1, 4, 5, 3, 2])
trees2 = list (trees1)
trees2.sort()
if trees1 == trees2:
    print ('trees1 is SORTED')
else:
    print ('Not sorted')