使用除法和impera算法检查向量是否有序

2024-05-15 • 问答

我试图检查是否使用分而治之算法对向量进行排序，这是我到目前为止编写的代码：

#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};
cout << isOrdered(v,v.size() - 1);
return 0;
}

它似乎不适用于某些情况，并且在调试时我不断添加特定的基本情况以使其适用于一个输入，但是这并不能使其适用于另一个输入，直到我意识到我已经算法错误。我基本上是这样想的：将向量划分为子向量，如果所有子向量都被排序，则整个向量都将被排序。但是，这种方法很快就失效了。如果输入长度不是2的幂，则它将最终将其分解为某些长度为1的子矢量，这些子矢量将始终被排序。例如，如果输入是2 2 3 2 2，该怎么办？子向量是{2，2}，{3}和{2，2}，它们都是有序的，但整个向量不是。

那么我应该怎么看待这个问题呢？我尝试通过添加return v[left-1] <= v[left];行使其长度为1的子向量起作用，但是它仍然崩溃。

从递归开始：

如果两个子范围都被排序，则

范围被排序，如果“低”范围的最后一项低于“高”范围的第一项，则：

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,mid - 1)
            && isOrdered(v,right);
    }
}

您为什么还要使用这种“困难”算法？为了检查矢量是否是有效的，每个成员（v[i]）都不能大于下一个成员（v[i+1]）。

“分而治之”算法更有用，例如，在已经排序的矢量中查找某些东西，但是对于检查矢量是否有序，简单的线性算法会更好（由于可读性好））。

#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,mid) && isOrdered(v,mid+1,right);
}

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

使用除法和impera算法检查向量是否有序

adsaad 回答：使用除法和impera算法检查向量是否有序

大家都在问