草庐IT

c++ - 双向插入排序错误

coder 2024-02-19 原文

我正在尝试进行双向插入排序。它应该获取数组中的第一个值，然后通过将其与第一个值进行比较来对数组中的以下数字进行排序。如果数字较大，则放在数组中第一个数字的后面，如果数字较小，则放在前面。

这是一张说明该过程的图片。

这里的数组是6 5 3 1 8 7 2 4，从上往下读就是排序过程的每一步。它将数字 6 与其余数字进行比较，然后相应地放置它们。

到目前为止我有这段代码:

void twowaysort(int n, int a[])
{
    int j;
    int first = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > first) {
            j = i + 1;
            while (j <= n - 1 && a[j] < a[j - 1]) {
                swap(a[j - 1], a[j]);
                j = j + 1;
            }
        }
        if (a[i] < first) {
            j = i - 1;
            while (j >= 0 && a[j] > a[j + 1]) {
                swap(a[j + 1], a[j]);
                j = j - 1;
            }
        }
    }
}

虽然这适用于上面的数组，但它似乎无法对以下内容进行排序:13 93 58 33 58 63 11 41 87 32。这让我相信某处存在错误。

如有任何帮助，我们将不胜感激。

最佳答案

我注意到的第一件事是即使有一个选定的值，也没有相应的选定索引。所以必须添加和使用它。

第二件事是所选值只是一个边界。每次当前排序的值都必须冒泡时，它就会下降。

所以总而言之，这只是一个标准的插入排序。 (也就是说，如果我正确理解算法的话。)

将变量 i 和 j 重命名为 to_sort_idx 和 look_at_idx。

void twowaysort( int a_size, int a[] )
{
    if ( a_size < 2 )
        return;

    int selected_idx   = 0;
    int selected_value = a[ selected_idx ];

    for ( int to_sort_idx = 1; to_sort_idx < a_size; to_sort_idx++ )
    {
        if ( a[ to_sort_idx ] > selected_value )
        {
            int look_at_idx = to_sort_idx;

            while ( look_at_idx > selected_idx && a[ look_at_idx ] < a[ look_at_idx - 1] )
            {              
                std::swap( a[ look_at_idx -1 ], a[ look_at_idx  ] );
                --look_at_idx;
            }
        }
        else //if ( a[ to_sort_idx ] <= selected_value )
        {
            int look_at_idx = to_sort_idx - 1;

            while ( look_at_idx >= 0 && a[ look_at_idx ] > a[ look_at_idx + 1 ] )
            {
                std::swap( a[ look_at_idx ], a[ look_at_idx + 1] );
                --look_at_idx;
            }

            ++selected_idx;
        } 
    }
}

关于c++ - 双向插入排序错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50391605/

amp43look_at_idxidxlookc++algorithmsortinginsertion-sorttwo-way

有关c++ - 双向插入排序错误的更多相关文章

  1. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

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

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

  3. ruby-on-rails - 迷你测试错误 : "NameError: uninitialized constant" - 2

    我遵循MichaelHartl的“RubyonRails教程:学习Web开发”，并创建了检查用户名和电子邮件长度有效性的测试(名称最多50个字符，电子邮件最多255个字符)。test/helpers/application_helper_test.rb的内容是:require'test_helper'classApplicationHelperTest在运行bundleexecraketest时，所有测试都通过了，但我看到以下消息在最后被标记为错误:ERROR["test_full_title_helper",ApplicationHelperTest,1.820016791]test

  4. ruby-on-rails - 如何在 Rails View 上显示错误消息？ - 2

    我是rails的新手，想在form字段上应用验证。myviewsnew.html.erb.....模拟.rbclassSimulation{:in=>1..25,:message=>'Therowmustbebetween1and25'}end模拟Controller.rbclassSimulationsController我想检查模型类中row字段的整数范围，如果不在范围内则返回错误信息。我可以检查上面代码的范围，但无法返回错误消息提前致谢 最佳答案 关键是您使用的是模型表单，一种显示ActiveRecord模型实例属性的表单。c

  5. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

    我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常，除了该文件不是公开可用的，而且我无法获得它的公共(public)URL。但是当我登录到S3时，我可以正常查看我的文件。为了使其公开可用，我将最后一行更改为obj.upload_file(file

  6. ruby-on-rails - 错误 : Error installing pg: ERROR: Failed to build gem native extension - 2

    我克隆了一个rails仓库，我现在正尝试捆绑安装背景:OSXElCapitanruby2.2.3p173(2015-08-18修订版51636)[x86_64-darwin15]rails-v在您的Gemfile中列出的或native可用的任何gem源中找不到gem'pg(>=0)ruby​​'。运行bundleinstall以安装缺少的gem。bundleinstallFetchinggemmetadatafromhttps://rubygems.org/............Fetchingversionmetadatafromhttps://rubygems.org/...Fe

  7. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  8. ruby-on-rails - 每次我尝试部署时，我都会得到 - (gcloud.preview.app.deploy) 错误响应 : [4] DEADLINE_EXCEEDED - 2

    我是Google云的新手，我正在尝试对其进行首次部署。我的第一个部署是RubyonRails项目。我基本上是在关注thisguideinthegoogleclouddocumentation.唯一的区别是我使用的是我自己的项目，而不是他们提供的“helloworld”项目。这是我的app.yaml文件runtime:customvm:trueentrypoint:bundleexecrackup-p8080-Eproductionconfig.ruresources:cpu:0.5memory_gb:1.3disk_size_gb:10当我转到我的项目目录并运行gcloudprevie

  9. ruby-on-rails - Rails 5 Active Record 记录无效错误 - 2

    我有两个Rails模型，即Invoice和Invoice_details。一个Invoice_details属于Invoice，一个Invoice有多个Invoice_details。我无法使用accepts_nested_attributes_forinInvoice通过Invoice模型保存Invoice_details。我收到以下错误:(0.2ms)BEGIN(0.2ms)ROLLBACKCompleted422UnprocessableEntityin25ms(ActiveRecord:4.0ms)ActiveRecord::RecordInvalid(Validationfa

  10. arrays - 这是 Ruby 中 Array.fill 方法的错误吗？ - 2

    这个问题在这里已经有了答案:Arraysmisbehaving(1个回答)关闭6年前。是否应该这样，即我误解了，还是错误？a=Array.new(3,Array.new(3))a[1].fill('g')=>[["g","g","g"],["g","g","g"],["g","g","g"]]它不应该导致:=>[[nil,nil,nil],["g","g","g"],[nil,nil,nil]]

随机推荐