arrays - 检查数组是否使用分治法排序

Question

正如问题所说，我需要用 C 或 Python 编写一个算法，它使用分而治之来检查数组是否已排序。我有一个基本的想法，但我似乎无法得出一个明确的答案。这是我到目前为止得到的，使用伪代码：

isSorted(array, start, end):
    if (len(array)) <= 1: return true
    if (end - start) == 1: return array[end] > array[start]
    middle = (end + start) // 2
    return isSorted(array, start, middle) && isSorted(array, middle, end)

这能行吗？还是我错过了一些该算法不起作用的边界情况？

标签： arrayssortingpseudocodedivide-and-conquer

Answer 1

找到了我自己的问题的答案，我在那里，但在评论中标记了一些问题。其中之一是当数组中有重复项时我没有处理，并且 len(array) 无法正常工作，因为我从未更改过数组。

def isSorted(array, start, end):
    if start == end: return True
    if (end - start) == 1: return array[end] >= array[start]
    middle = (end + start) // 2
    return isSorted(array, start, middle) and isSorted(array, middle, end)

这是用 Python 编写的，非常接近上面的伪代码，它适用于我制作的案例。