C++中的插入排序算法

Question

我正在为 C++ 中的排序创建一个插入算法。这是：

void mySort2(int a[], const int num_elements)
{
    int x[num_elements];
    bool inserted(false);

    x[0] = a[0];

    for(int i = 1; i < num_elements; i++)
    {
        inserted = false;
        for(int j = 0; j < i; j++)
        {
            if(a[i] < x[j])
            {
                inserted = true;
                memmove(x + j + 1, x+j, (num_elements - j - 1)*sizeof(int*));
            x[j]=a[i];
                break;
            }
        }
        if(!inserted)
        {
            x[i] = a[i];
        }
    }

    print(x, num_elements);
}

用数据集测试时：

int num_elements(7);
int a[] = {2, 1, 3, 7, 4, 5, 6};

代码按预期工作，打印 1、2、3、4、5、6、7 但是，当我使输入大于 7 时，程序会出现分段错误并转储核心。我试过小于 7 个元素的数据集，它再次按预期工作。

我是否需要使用动态分配的内存，或者我的算法是否存在错误？

谢谢！

Answer 1

sizeof(int*) 可能不等于 sizeof(int)。不管是不是，你的意思是写 sizeof(int)。您可能移动了太多数据并占用了一些随机内存。

哦，为了好玩，这里有一个次优的（但代码太少了！）插入排序：

for(auto i = first; i != last; ++i)
    std::rotate(std::upper_bound(first, i, *i), i, std::next(i));

C++中的插入排序算法

Insertion sorting algorithm in C++

c++

sorting

algorithm

insertion-sort