这是插入排序吗？

Question

我正在读“算法导论”和关于插入排序的内容。

我尝试在没有阅读他们的解决方案的情况下自己实现它。

这是我的解决方案，这是插入排序吗？

#include <iostream>

using namespace std;

int main()
{
    // initialize an unsorted array
    int a[] = {5,6,4,7,3,8,2,9,0,1};

    // define variables
    int i,j,tmp;

    for (int j=1; j<10; ++j)
    {
        for (int i=0;i<j;++i)
        {
            if (a[j] < a[i])
            {
                tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
            }
        }

    }

    for (i=0;i<10;++i)
    {
        cout << a[i] << endl;
    }

    return 0;
}

好的，我已经读过了，并且理解为什么它不是插入排序...这样就好多了。

   #include <iostream>

    using namespace std;

    int main()
    {
        // initialize an unsorted array
        int a[] = {5,6,4,7,3,8,2,9,0,1};

        // define variables
        int i,j,key,c;

        for (int j=1; j<10; ++j)
        {
            key = a[j];
            i = j - 1;

            while(i>=0 && a[i] > key)
            {
                a[i+1] = a[i];
                i = i - 1;
            }
            a[i+1] 

= key;
        ++c;
    }

    for (i=0;i<10;++i)
    {
        cout << a[i] << endl;
    }

    cout << endl << c << endl;
    return 0;
}

Answer 1

您的解决方案似乎是冒泡排序，而不是插入排序。

Answer 2

对我来说它看起来像是插入排序。您一次只能创建一个元素的排序数组(a[0...j])。

你的插入很不寻常，而且效率很低。要将a[j]插入到a[0...j]中，您不需要将其与每个元素进行比较。