检查列表是否排序的 Python 方法

正如@aaronsterling 指出的，下面的解决方案是最短的，当数组被排序时似乎是最快的，而且不是太小: Def is _ sort (lst) : Return (sort (lst) = = lst)

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

def is_sorted(lst):
it = iter(lst)
try:
prev = next(it)
except StopIteration:
return True
for x in it:
if prev > x:  # For reverse, use <
return False
prev = x
return True

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

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

排序(lst) = = lst 解

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

第二个解决方案:

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

虽然我认为不能保证 sorted内置函数能够使用 i+1, i调用它的 cmp 函数，但是对于 CPython 似乎确实可以这样做。

所以你可以这样做:

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

或者这样(没有 if 语句-> 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

一点也不 Python，但我们至少需要一个 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')

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

我会这么做(窃取很多答案(亚伦•斯特林(Aaron Sterling)、伟业通(Wei Yip Tung) ，有点像保罗•麦圭尔(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))

一个好处是: 您不必实现该系列的第二个迭代(与列表切片不同)。

我使用这个基于 numpy.diff ()的一行程序:

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

我还没有真正将它与其他方法进行计时，但是我假设它比任何纯 Python 方法都要快，特别是对于大 n，因为 numpy.diff 中的循环(可能)直接在 C 中运行(n-1减法后跟 n-1比较)。

但是，如果 x 是一个无符号整型数，则需要小心，这可能会导致 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()

实现这一点的一个漂亮方法是使用来自 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))

这个实现速度很快，可以在任何可迭代文件上工作。

在 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.')

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

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

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

懒惰

from itertools import tee


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

这里使用递归:

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


some_list = [1,2,3,4]
print(is_sorted(some_list))

注意，对于长序列，这将提高 RuntimeError: maximum recursion depth exceeded。

这与最上面的答案类似，但我更喜欢它，因为它避免了显式索引。假设您的列表名为 lst，您可以使用 zip从列表中生成 < br > (item, next_item)元组:

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

在 Python3中，zip已经返回了一个生成器，在 Python2中，您可以使用 itertools.izip来提高内存效率。

小演示:

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

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

额外奖励: 检查无法被索引的有限(!)生成器:

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

如果您使用的是 Python2，请务必在这里使用 itertools.izip，否则您将无法实现不必从生成器创建列表的目的。

如果您想要用最快的方法处理 numpy 数组，可以使用 笨蛋，如果使用 conda，则应该已经安装了 笨蛋

代码会很快，因为它是由 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

然后:

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

只是添加另一种方式(即使它需要一个额外的模块) :

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


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

检查 DESC 命令:

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


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

还有一个 strict参数，如果你需要检查严格(如果连续的元素不应该是相等的)单调序列。

这在你的情况下不是问题，但是 如果你的序列包含 nan值，然后一些方法会失败，例如排序:

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


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


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

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

这个怎么样? 简单明了。

def is_list_sorted(al):


llength =len(al)




for i in range (llength):
if (al[i-1] > al[i]):
print(al[i])
print(al[i+1])
print('Not sorted')
return -1


else :
print('sorted')
return  true

最简单的方法:

def isSorted(arr):
i = 1
while i < len(arr):
if(result[i] < result[i - 1]):
return False
i += 1
return True

Python 3.6.8

from more_itertools import pairwise


class AssertionHelper:
@classmethod
def is_ascending(cls, data: iter) -> bool:
for a, b in pairwise(data):
if a > b:
return False
return True


@classmethod
def is_descending(cls, data: iter) -> bool:
for a, b in pairwise(data):
if a < b:
return False
return True


@classmethod
def is_sorted(cls, data: iter) -> bool:
return cls.is_ascending(data) or cls.is_descending(data)

>>> AssertionHelper.is_descending((1, 2, 3, 4))
False
>>> AssertionHelper.is_ascending((1, 2, 3, 4))
True
>>> AssertionHelper.is_sorted((1, 2, 3, 4))
True

from functools import reduce


# myiterable can be of any iterable type (including list)
isSorted = reduce(lambda r, e: (r[0] and (r[1] or r[2] <= e), False, e), myiterable, (True, True, None))[0]

导出的还原值是(SortedSoFarFlag，FirstTimeFlag，LastElementValue)的三部分元组。它最初以(True、 True、 None)开始，这也被用作空列表的结果(因为没有无序元素而被认为是有序的)。在处理每个元素时，它计算元组的新值(使用前一个元组值和下一个元素值) :

[0] (sortedSoFarFlag) evaluates true if: prev_0 is true and (prev_1 is true or prev_2 <= elementValue)
[1] (firstTimeFlag): False
[2] (lastElementValue): elementValue

减少的最终结果是一个元组:

[0]: True/False depending on whether the entire list was in sorted order
[1]: True/False depending on whether the list was empty
[2]: the last element value

第一个值是我们感兴趣的值，所以我们使用 [0]从 reduce 结果中获取它。

因为我没有看到这个选项上面我将添加到所有的答案。 让我们用 l表示列表，然后:

import numpy as np


# Trasform the list to a numpy array
x = np.array(l)


# check if ascendent sorted:
all(x[:-1] <= x[1:])


# check if descendent sorted:
all(x[:-1] >= x[1:])

使用赋值表达式的解决方案(在 Python 3.8中添加) :

def is_sorted(seq):
seq_iter = iter(seq)
cur = next(seq_iter, None)
return all((prev := cur) <= (cur := nxt) for nxt in seq_iter)


z = list(range(10))
print(z)
print(is_sorted(z))


import random
random.shuffle(z)
print(z)
print(is_sorted(z))


z = []
print(z)
print(is_sorted(z))

给予:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
True
[1, 7, 5, 9, 4, 0, 8, 3, 2, 6]
False
[]
True

从 Python 3.10开始，新的 pairwise函数提供了一种方法来滑动连续的元素对，从而发现是否所有这些元素对都满足相同的顺序谓词:

from itertools import pairwise


all(x <= y for x, y in pairwise([1, 2, 3, 5, 6, 7]))
# True

pairwise的中间结果:

pairwise([1, 2, 3, 5, 6, 7])
# [(1, 2), (2, 3), (3, 5), (5, 6), (6, 7)]

第三方软件包方法 more_itertools.is_sorted还没有被提及:

import more_itertools


ls = [1, 4, 2]


print(more_itertools.is_sorted(ls))


ls2 = ["ab", "c", "def"]


print(more_itertools.is_sorted(ls2, key=len))

这种使用熊猫的方法非常缓慢，但是它以完整性著称。

from typing import Sequence


import pandas as pd


def is_sorted(seq: Sequence, reverse: bool = False) -> bool:
index = pd.Index(seq)
if reverse:
return index.is_monotonic_decreasing
return index.is_monotonic_increasing

试试这个:

def is_sorted(arr) -> bool:
for i in range(1, len(arr)):
if arr[i] < arr[i - 1]:
return False
return True