草庐IT

【数据结构与算法】快速排序的非递归实现方法

sukuni 2023-07-09 原文

 

目录

一.前言

二.非递归实现

一.前言

如果数据量过大的话，不断递归就会出现栈溢出的现象，这个时候你的代码是没问题的，但就是跑不起来，这个时候就要把递归改成非递归。

一般有两种改法：

1.直接改，利用循环等；

2.借助栈的辅助。

而快速排序的非递归实现方法就需要借助栈的辅助。

二.非递归实现

通过观察我们发现，每次递归调用传过去的是一个数组和一个区间，数组自不用说，这个区间就是我们的突破点；

也就是说我们只要想办法在循环的时候拿到本次要排序的区间就行了，那要怎么做呢？

借助数据结构：栈，栈具有后进先出的特性，借助这个就能很好的解决问题。

1.首先要先把 left 和 right 入栈，这样栈此时就不为空，然后开始循环。

2.取出栈顶的两个数据，分别赋给 begin 和 end ，注意在这之后要pop掉取出的数据；

3.然后就是快排的逻辑，有三种方法，哪种都可以；

   如果不清楚这三种方法的话，请点击：快速排序的三种实现方法

   走完一趟后就得到了 keyi；

4.然后数组就被 keyi 分成了两个子区间，分别是：

     左区间：[begin，keyi-1]

     右区间：[keyi+1，end]

 分别将左区间和右区间入栈，注意这里要判断：

       a.keyi+1<end

       b.keyi-1>begin

否则会出现数组访问越界或是死循环的情况。

5.因为栈是后进先出，所以要是想先排左区间的话，就要先入右区间进栈，反之；

6.循环结束后，销毁栈。

void QuickSortNonR(Sdatatype* arr, int left, int right)
{
	ST st;
	Stackinit(&st);
	
	Stackpush(&st, right);
	Stackpush(&st, left);
	while (!Stackempty(&st))   //栈为空时就结束循环
	{
		int begin = Stacktop(&st);   //出一个就要pop掉一个数据
		Stackpop(&st);
		int end = Stacktop(&st);
		Stackpop(&st);
		int keyi = begin;    //以下为快速排序的逻辑，这里用的是前后指针法实现
		int mid = GetMid(arr, begin, end);
		if (mid != keyi)
			Swap(&arr[mid], &arr[keyi]);
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi])
			{
				prev++;
				Swap(&arr[cur], &arr[prev]);
				cur++;
			}
			else
				cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;   
		if (keyi + 1 < end)    //不要忘记判断
		{
			Stackpush(&st, end);    //这里是先入的右区间，所以是先排序左区间
			Stackpush(&st, keyi + 1);
		}
		if (keyi - 1 > begin)
		{
			Stackpush(&st, keyi - 1);
			Stackpush(&st, begin);
		}
	}

	Stackdestroy(&st);   //销毁栈
}

🐬🤖本篇文章到此就结束了，若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻

😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩

😍😁谢谢你的阅读。😸😼

 

数据结构数据spanbackground-colorbackground排序算法算法c语言栈

有关【数据结构与算法】快速排序的非递归实现方法的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  6. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  7. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  8. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  9. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  10. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

随机推荐