草庐IT

c++ - 插入排序还是选择排序的变体？

coder 2024-02-17 原文

我有一个代码片段 here .测试了几个案例，似乎工作正常。

学习了算法后，我一下子写出了插入排序的代码，但是有疑问，这真的是传统的插入排序吗？

我觉得这可能是选择排序的变体(调整版)，这是我困惑的原因。

具体来说，这是值得关注的领域:(给定 n 元素的数组 a)

for(i=1;i<n;i++){
    for(j=0;j<i;j++){
        if(a[i] < a[j]){
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }      
}

此外，这种方法的比较或交换次数是多了还是少了？

在此先感谢您的帮助。

最佳答案

你的问题最直接的答案是是，就是插入排序。这是一种非常低效的插入排序，但它仍然是插入排序。

您的代码缺少决定性的步骤，即一旦确定元素的位置，就可以停止比较，然后对已排序的序列进行移位操作，从而为新元素打洞。相反，您依靠比较循环为您执行该转换，即使不再需要比较时也是如此，这不是很有效。

这可能看起来有点令人困惑，所以我将针对您的代码进行详细说明。

  • i 每次迭代的前景元素最初是 a[i]。
  • 您对序列中已排序的部分进行线性枚举，寻找 a[i] 所属的位置
  • 一旦找到位置(除非它已经在它所属的位置)，您将 a[i] 与当前位于您的位置的元素 a[j] 交换目标。
  • 从那时起，a[i] 的原始值现在就位在序列中，但是...
  • 对于排序序列的其余部分，交换比较保证触发为真(提示:为什么要这样做？)针对存储在 a[i] 中的任何值，因为值之前成功的它已经被排序了。因此，a[i] 不断被排序序列中的下一个值替换，直到它最终拥有最大值，这是它所属的定义。

因此，是的，这就是插入排序。它在整体的开始处维护一个排序序列，该序列随着每次主要迭代而不断扩展。对于每个主要迭代，前景元素都被“插入”，尾随元素被向下移动以形成可用的孔来执行此操作。

... are the number of comparisons or swaps more/less with this kinda approach?

相当多您的方法需要更多的比较。每次迭代都保证线性 O(n) 复杂度，并且有 n 次迭代。因此，保证您的比较具有O(N^2) 复杂性，这是低效排序算法的祸害。不仅仅是最坏的情况； 保证。

C++ 插入排序

也就是说，考虑一下

template<typename Iter>
void insertion_sort(Iter first, Iter last)
{
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

那可能是seems like Greek (没有冒犯希腊人的意思)如果你刚开始使用 C++，但它利用了两种基本算法，使其效率惊人:std::upper_bound 和 std::rotate .

std::upper_bound对排序序列进行操作。利用这一点，它可以利用二进制搜索 算法来定位排序序列中严格大于预期值 (*it) 的第一个元素。因此，为单个前景搜索插入点的时间为 O(logN)，远优于 O(n) 的线性搜索。

一旦插入点已知，std::rotate用于通过使用插入点的迭代器将元素放置到位。它有效地做到了这一点:

0 1 2 3 5 6 4
        ^ ^ *  these will be rotated right one element

0 1 2 3 5 6 
            4

0 1 2 3   5 6 
        4

0 1 2 3 4 5 6

请注意，旋转需要不比较。

显然，此模板解决方案不是某些补救算法类(class)的人会提交的内容。但我希望它能给你一些关于插入排序如何通过以下方式最小化比较的想法:

  • 对序列的已排序部分使用二分查找，以尽量减少比较。
  • 执行旋转时不使用比较。

关于c++ - 插入排序还是选择排序的变体？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41784725/

变体ampcode的sectionc++algorithmsortinginsertion-sort

有关c++ - 插入排序还是选择排序的变体？的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - Rails 3 的 RGB 颜色选择器 - 2

    状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2

    我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or

  6. ruby-on-rails - Rails 单选按钮 - 模型中多列的一种选择 - 2

    我希望用户从一个模型的三个选项中选择一个。即我有一个模型视频，可以被评为正面/负面/未知目前我有三列bool值(pos/neg/unknown)。这是处理这种情况的最佳方式吗？为此，表单应该是什么样的？目前我有类似的东西但显然它允许多项选择，而我试图将它限制为只有一个..怎么办？ 最佳答案 如果要使用字符串列，让我们说rating。然后在你的表单中:#...#...它只允许一个选择编辑完全相同但使用radio_button_tag: 关于ruby-on-rails-Rails单选按钮-模

  7. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  8. ruby-on-rails - Ruby 流量控制 : throw an exception, 返回 nil 还是让它失败？ - 2

    我在思考流量控制的最佳实践。我应该走哪条路？1)不要检查任何东西并让程序失败(更清晰的代码，自然的错误消息):defself.fetch(feed_id)feed=Feed.find(feed_id)feed.fetchend2)通过返回nil静默失败(但是，“CleanCode”说，你永远不应该返回null):defself.fetch(feed_id)returnunlessfeed_idfeed=Feed.find(feed_id)returnunlessfeedfeed.fetchend3)抛出异常(因为不按id查找feed是异常的):defself.fetch(feed_id

  9. ruby - 如何在 Ruby 字符串中插入项目符号字符？ - 2

    我正在尝试创建一个带有项目符号字符的Ruby1.9.3字符串。str="•"+"helloworld"但是，当我输入它时，我收到有关非ASCII字符的语法错误。我该怎么做？ 最佳答案 你可以把Unicode字符放在那里。str="\u2022"+"helloworld" 关于ruby-如何在Ruby字符串中插入项目符号字符？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1195

  10. ruby-on-rails - CarrierWave - PDF - 只选择第一页 - 2

    我的Rails应用程序中安装了carrierwave。但是，当用户上传多页pdf时，我只希望应用程序获取文档中的第一页并将其转换为jpeg。这可能吗？用什么命令？这是我的uploader。#encoding:utf-8classImageUploader[200,300]##defscale(width,height)##dosomething#end#Createdifferentversionsofyouruploadedfiles:version:thumbdoprocess:resize_to_fill=>[150,210]process:convert=>:jpgdefful

随机推荐