一次检查列表是否按升序或降序排序

Question

有没有办法一次检查列表是按升序还是降序排序？

从this answer开始，我修改为也支持降序检查，所以我的代码现在是这样的，有没有办法不用两个for循环就可以检查这个？

def is_sorted(check):
    current = check
    forwarded = check[1:]
    ascending_check = all(i<=j for i, j in zip(current, forwarded))
    descending_check = all(i>=j for i, j in zip(current, forwarded))
    return ascending_check or descending_check

numbers = list(range(1, 10))
print(is_sorted(numbers))
reverse_numbers = list(range(10, 0, -1))
print(is_sorted(reverse_numbers))
not_sorted = [1, 3, 2, 4, 5]
print(is_sorted(not_sorted))

Answer 1

您可以尝试检查是否按升序排序，如果不是：array[::-1]，然后再次检查。 array[::-1] 反转数组。

Answer 2

您可以检查成对的连续元素，跟踪不是 == 的第一对是 < 还是 >，并检查所有其他对是否具有相同的关系（如果不相等）：

def is_sorted(lst):
    asc = None
    for i in range(len(lst)-1):
        a, b = lst[i], lst[i+1]
        if a == b:
            continue
        if asc is None:
            asc = (a < b)
        if (a < b) != asc:
            return False
    return True

这有点冗长，但您也可以使用 next 和 all 来缩短它，对两者使用共享的 zip 迭代器，这样整个列表只迭代一次。

def is_sorted(lst):
    pairs = zip(lst, lst[1:])
    asc = next((a < b for a, b in pairs if a != b), None)
    return asc is None or all((a < b) == asc for a, b in pairs if a != b)

但是，此版本（与您的原始版本一样）将使用 lst[1:] 创建输入列表的副本，因此这也不仅仅是一个循环。要解决这个问题，您可以例如使用 itertools.tee 或 islice.

Answer 3

您可以检查前两个元素，然后 return True 如果整个列表与这两个元素的顺序相同。您还必须考虑到开头有平局的可能性，并且整个列表始终只包含相同的值。

def is_sorted(check):
    ascending = True
    descending = True
    previous = check[0]
    for item in check[1:]:
        if ascending and item < previous:
            ascending = False
        if descending and item > previous:
            descending = False
        if not ascending and not descending:
            return False
        previous = item
    return True

演示：https://ideone.com/YjBB9T

Answer 4

这可行：

def is_sorted(check):
    asc = desc = True
    i, L = 0, len(check)
    while (i < (L-1)) and (asc or desc):
        if check[i] < check[i+1]:
            desc = False
        elif check[i] > check[i+1]:
            asc = False
        if not (asc or desc):
            break
        i += 1
    if asc and desc:
        return "Ascending and Descending"
    elif asc:
        return "Ascending"
    elif desc:
        return "Descending"
    else:
        return "Not ascending and not descending"

测试：

print (is_sorted([1, 2, 3]))
print (is_sorted([3, 2, 1]))
print (is_sorted([1, 2, 3, 2, 1]))
print (is_sorted([1, 1, 1]))

输出：

Ascending
Descending
Not ascending and not descending
Ascending and Descending

一次检查列表是否按升序或降序排序

Check if list is sorted in either ascending or descending order in one pass

python

sorting

time-complexity