-1

直接包含排序的另一个名称是什么，相同排序的算法是什么？

我一直试图在互联网上搜索，但我没有得到一个直接的答案，但我找不到任何答案。我发现了这种用于直接插入排序的算法，并且在一些书中说它们与直接直接包含排序相同，但我对此表示怀疑，因为这本书是俄语的，所以我想确认（也就是说，如果它是真的或者我可能有翻译错误？）

C++ 中的代码：

int main(int argc, char* argv[])
{
    int arr[8] = {27, 412, 71, 81, 59, 14, 273, 87},i,j;

    for (j=1; j<8; j++){
        if (arr[j] < arr[j-1]) {
            //Что бы значение j мы не меняли а работали с i
            i = j;
            //Меняем местами пока не найдем нужное место
            do{
                swap(arr[i],arr[i-1]);
                i--;
                //защита от выхода за пределы массива
                if (i == 0)
                    break;
            }
            while (arr[i] < arr[i-1]) ;
        }
        for (i=0;i<8;i++)
            cout << arr[i]<< ' ';
        cout << '\n';
    }
    getch();
    return 0;
}

结果

27 412 71 81 59 14 273 87
27 71 412 81 59 14 273 87
27 71 81 412 59 14 273 87
27 59 71 81 412 14 273 87
14 27 59 71 81 412 273 87
14 27 59 71 81 273 412 87
14 27 59 71 81 87 273 412
4

3 回答 3

2

发布的代码是插入排序。

大多数实现会将乱序元素复制到临时变量，然后向后工作，向上移动元素，直到找到正确的开放点以“插入”当前元素。这就是维基百科文章中的伪代码显示的内容。

一些实现只是将无序元素向后冒泡，而它小于其左侧的元素。这就是do...while已发布代码中的内部循环所显示的内容。

这两种方法都是实现插入排序的有效方法。

于 2012-09-09T06:16:26.683 回答
1

您发布的代码看起来不像插入排序算法，因为您正在重复交换两个相邻元素。

您的代码看起来更像某种冒泡排序。

这里列出了常见的排序算法： https ://en.wikipedia.org/wiki/Sorting_algorithm

“直接插入”和“直接包含”听起来几乎相同..所以我怀疑它们可能是同一算法的不同名称。

编辑：可能“直接”前缀应该表示只使用一个容器..但是，如果交换了两个相邻元素，我不会称之为插入排序，因为根本没有“插入”。

于 2012-09-09T05:33:09.223 回答
0

鉴于术语“直接包含排序”根本不会产生谷歌点击，而“直接插入排序”只有 27 次点击，其中前三个是这里的帖子和两个相同措辞的博客 帖子，我怀疑这个术语有任何被广泛接受的含义。所以你的问题中关于

有些书说它们与直接直接包含排序相同

很难回答，除非我们找到直接包含排序实际上是什么的明确定义。

于 2012-09-09T08:47:57.933 回答