递归插入排序中出现分段错误

Question

我试图编写插入排序的递归代码，但出现分段错误。请帮我解决这个问题。

#include <bits/stdc++.h>

using namespace std;

void insert(vector<int> &v,int temp){
    if(v.size()==0||v[v.size()-1]<=temp){
        v.push_back(temp);
        return;
    }
    int val = v[v.size()-1];
    v.pop_back();
    insert(v, temp);
    v.push_back(val);
    return;
}

void sort(vector<int> &v){
    if(v.size()==1) return;
    int temp = v[v.size()-1];
    v.pop_back();
    sort(v);
    insert(v,temp);
}

int main() {
    int n;
    vector<int> v;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>v[i];
    sort(v);
    for(int i=0;i<n;i++)
    cout<<v[i];
    return 0;
}

Answer 1

这将创建一个空的 vector：

vector<int> v;

访问其中的任何元素将使您的程序具有 未定义行为。
您可以通过向构造函数提供 n 或调用 resize(n) 来创建具有所需元素数量的 vector > 创建空的向量后。另一种选择是将其创建为空，然后到 push_back()< /code>或 emplace_back 元素放入其中，在这种情况下它将动态增长。

使用正确数量的元素创建它的示例：

int main() {
    int n;

    // verify that extraction of `n` succeeded and that `n > 0`:
    if(!(std::cin >> n && n > 0)) {
        std::cerr << "error\n";
        return 1;
    }

    // create the vector with the correct number of elements
    std::vector<int> v(static_cast<size_t>(n));

    // use a range-based for loop to get a reference to each element:
    for(int& val : v)
        std::cin >> val;    // extract into the referenced `int`

    sort(v);

    // here you can use a range-based for loop to get a copy of each element
    // (which is cheap in this case, since they are `int`s):
    for(int val : v)
       std::cout << val << ' ';
    std::cout << '\n';
}

演示

注意：

• #include < ;bits/stdc++.h> - 切勿包含此非标准标头。包含标准标头，例如 iostream 和 vector

• using namespace std; - 不要这样做。尤其是当您为 sort 等函数提供重载时，如果您包含 bits/stdc++.h 并执行 using namespace std;，这些函数就可用。

Answer 2

问题是向量v是空（意味着它的大小0），而你试图访问其元素会导致未定义的行为。

vector<int> v; //this creates an empty vector named v
cin>>n;
for(int i=0;i<n;i++)
cin>>v[i]; //this leads to undefined behavior

在上面的代码片段中，向量 v 是一个空向量，意味着它没有元素。所以表达式 cin >> v[i] 会导致未定义的行为，因为您正在访问向量的第 i 个索引处的元素，但向量内没有要访问的元素。

未定义的行为意味着任何¹都可能发生包括但不限于程序给出您的预期输出。但永远不要依赖（或根据）具有未定义行为的程序的输出。

因此，您看到的（也许看到的）输出是未定义行为的结果。正如我所说，不要依赖具有 UB 的程序的输出。该程序可能会崩溃（这就是您的情况）。

因此，使程序正确的第一步是删除 UB。 只有那时您才能开始推理程序的输出。

解决方案

要解决这个问题，您可以在创建向量时指定向量的大小，如下所示：

int n;
cin>>n;
vector<int> v(n);//create vector of size n

---

^{1有关未定义行为的更准确的技术定义，请参阅这里其中提到：对程序。}

Answer 3

您声明了一个空向量

int n;
vector<int> v;

，因此在此 for 循环中使用下标运算符

for(int i=0;i<n;i++)
cin>>v[i];

会调用未定义的行为。

相反，您可以在输入 n 的值后首先使用 n 元素声明向量，例如

int n;
cin>>n;
vector<int> v( n );
for(int i=0;i<n;i++)
cin>>v[i];

，或者您可以在输入 n< 的值之后调整向量的大小/code> 变得像 At 一样，

int n;
vector<int> v;
cin>>n;
v.resize( n );
for(int i=0;i<n;i++)
cin>>v[i];

最好将变量 n 声明为具有无符号整数类型，例如，

size_t n;

您可以使用基于范围的 for 循环代替 for 循环

size_t n = 0;
cin>>n;

std::vector<int> v( n );

for ( auto &item : v ) std;:cin >> item;

在函数 sort 中，您 可以使用基于范围的 for 循环。需要至少按以下方式更改 if 语句中的条件

void sort( std::vector<int> &v ){
    if ( v.size() < 2 ) return;
    //...

，因为通常用户可以传递一个空向量。

您可以使用成员函数 back，而不是使用像 v[v.size()-1] 这样的表达式。例如，

int temp = v.back();

这使代码更具可读性。

我将按以下方式定义函数，而不使用多余的返回语句

void insert( std::vector<int> &v, int value )
{
    if (v.empty() || not( value < v.back() ) )
    {
        v.push_back( value );
    }
    else
    {
        int tmp = v.back();
        v.pop_back();
        insert( v, value );
        v.push_back( tmp );
    }
}

void sort( std::vector<int> &v )
{
    if (not ( v.size() < 2 ))
    {
        int last = v.back();
        v.pop_back();
        sort( v );
        insert( v, last );
    }
}

这是一个演示程序。

#include <iostream>
#include <vector>

void insert( std::vector<int> &v, int value )
{
    if (v.empty() || not( value < v.back() ) )
    {
        v.push_back( value );
    }
    else
    {
        int tmp = v.back();
        v.pop_back();
        insert( v, value );
        v.push_back( tmp );
    }
}

void sort( std::vector<int> &v )
{
    if (not ( v.size() < 2 ))
    {
        int last = v.back();
        v.pop_back();
        sort( v );
        insert( v, last );
    }
}

int main()
{
    std::vector<int> v = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    sort( v );

    for (const auto &item : v)
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

程序输出是

0 1 2 3 4 5 6 7 8 9

建议：尽量避免使用 using 指令

using namespace std;

，它可能是名称冲突的原因，有时会使代码不清楚是否使用了标准 C++ 函数或用户定义的函数。