使用 divide et impera 算法检查向量是否有序

Question

我正在尝试检查向量是否使用分而治之算法排序，这是我目前编写的代码：

#include <iostream>
#include <vector>

using namespace std;

bool isOrdered(std::vector <int> v, int left, int right)
{
int mid = (left + right)/2;

if (left == right){
    if (left == 0)
        return true;
    else
        return v[left-1] <= v[left];
}
else if (left + 1 == right)
{
    if (v[left] <= v[right])
        return true;
    else
        return false;
}
else if (left > right)
{
    if (v[left] > v[right])
        return true;
    else
        return false;
}
else
{
    return isOrdered(v, left, mid) && isOrdered(v, mid+1, right);
}
}

int main()
{
std::vector <int> v = {2, 2, 3, 2, 2};
cout << isOrdered(v, 0, v.size() - 1);
return 0;
}

它似乎对某些情况不起作用，在调试时我不断添加特定的基本情况以使其适用于一个输入，但这不会使其适用于另一种输入，我一直这样做直到我意识到我有一个算法错误。我基本上是这样想的：将向量分成子向量，如果所有子向量都是有序的，那么整个向量都是有序的。然而，这种方法很快就会失效。如果输入长度不是 2 的幂，那么它最终会将其分解为某些长度为 1 的子向量，这些子向量始终是有序的。例如，如果输入是 2 2 3 2 2 怎么办？子向量是 {2, 2}、{3} 和 {2, 2}，它们都是有序的，但整个向量不是。

那么我应该怎么思考这个问题呢？我试图通过添加 return v[left-1] <= v[left]; 行使其适用于长度为 1 的子向量，但它仍然出现故障。

Answer 1

你为什么还要使用这个 "difficult" 算法？为了检查向量是否有序，每个成员 (v[i]) 不能大于下一个 (v[i+1])。

"divide-and-conquer"算法更有用，例如，在一个已经有序的向量中找到一些东西，但是对于检查一个向量是否有序，一个简单的线性算法要好得多（因为可读性).

Answer 2

#include <iostream>
#include <vector>

using namespace std;

bool isOrdered(const vector <int> &v, int left, int right) {
    int mid = (left + right)/2;
    if (left == right)
        return true;
    else
        return v[mid]<=v[mid+1] && isOrdered(v, left, mid) && isOrdered(v, mid+1, right);
}

int main()
{
    vector <int> v = {2, 2, 3, 2, 2};
    cout << isOrdered(v, 0, v.size() - 1);
    return 0;
}

Answer 3

从递归开始：

如果两个子范围都有序和如果 "low" 范围的最后一项低于 "high" 范围的第一项：

return isOrdered(v, left, mid - 1) && isOrdered(v, mid, right) && v[mid - 1] <= v[mid];

保持停止条件：当范围为空（不能从参数发生）或只有一个元素时。这些是有序的范围。

所以我们得到：

bool isOrdered(const std::vector<int>& v, std::size_t left, std::size_t right)
{
    if (left == right) { // Only one element
        return true;
    } else {
        const auto mid = (left + right + 1) / 2;
        return v[mid - 1] <= v[mid]
            && isOrdered(v, left, mid - 1)
            && isOrdered(v, mid, right);
    }
}

使用 divide et impera 算法检查向量是否有序

Check if a vector is ordered using divide et impera algorithm

c++

algorithm

recursion

vector

divide-and-conquer