blocks|key|2855638|text|递归并不总是比迭代慢。快速排序就是一个很好的例子。以迭代方式完成此操作的唯一方法是创建堆栈结构。所以在其他方面，如果我们使用递归，编译器也会做同样的事情，你可能会比编译器做得更糟。此外，如果不使用递归(将值弹出并推送到堆栈)，还会有更多的跳转。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2855639|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Recursion is NOT always slower than iteration. Quicksort is perfect example of it. The only way to do this in iterate way is create stack structure. So in other way do the same that the compiler do if we use recursion, and propably you will do this worse than compiler. Also there will be more jumps if you don't use recursion (to pop and push values to stack).

blocks|key|3069085|text|在(渐近)时间复杂度方面的-它们都是相同的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|3069086|“递归比迭代慢”--这句话背后的理性是因为递归堆栈的开销(在两次调用之间保存和恢复环境)。|3069087|然而，-these是恒定数量的操作，同时不改变“迭代”的数量。|3069088|递归和迭代快速排序都是O(nlogn)平均情况和O(n%5E2)最坏情况。|CODE|3069089|3069090|编辑：|3069091|只是为了好玩，我用附加到post的(java)代码运行了一个基准测试，然后我运行了wilcoxon+statistic+test，以检查运行时间确实不同的概率是多少|3069092|结果可能是确凿的(P值=2.6e-34，https://en.wikipedia.org/wiki/P-value。记住，P_VALUE是P(T+>=+t%7C+H)，其中T是检验统计量，H是零假设)。但答案并不是你所期望的。|3069093|迭代解的平均值为408.86毫秒，递归的平均值为236.81毫秒|3069094|(注意-我使用Integer而不是int作为recursiveQsort()的参数-否则递归会实现得更好，因为它不需要装箱很多整数，这也很耗时-我这样做是因为迭代解决方案别无选择，只能这样做。|3069095|因此-你的假设是不正确的，递归解决方案比P_VALUE=2.6e-34的迭代解决方案更快(对于我的机器和java来说是最小的)。|3069096|public+static+void+recursiveQsort(int[]+arr,Integer+start,+Integer+end)+{+
++++if+(end+-+start+<+2)+return;+//stop+clause
++++int+p+=+start+%2B+((end-start)/2);
++++p+=+partition(arr,p,start,end);
++++recursiveQsort(arr,+start,+p);
++++recursiveQsort(arr,+p%2B1,+end);

}

public+static+void+iterativeQsort(int[]+arr)+{+
++++Stack<Integer>+stack+=+new+Stack<Integer>();
++++stack.push(0);
++++stack.push(arr.length);
++++while+(!stack.isEmpty())+{
++++++++int+end+=+stack.pop();
++++++++int+start+=+stack.pop();
++++++++if+(end+-+start+<+2)+continue;
++++++++int+p+=+start+%2B+((end-start)/2);
++++++++p+=+partition(arr,p,start,end);

++++++++stack.push(p%2B1);
++++++++stack.push(end);

++++++++stack.push(start);
++++++++stack.push(p);

++++}
}

private+static+int+partition(int[]+arr,+int+p,+int+start,+int+end)+{
++++int+l+=+start;
++++int+h+=+end+-+2;
++++int+piv+=+arr[p];
++++swap(arr,p,end-1);

++++while+(l+<+h)+{
++++++++if+(arr[l]+<+piv)+{
++++++++++++l%2B%2B;
++++++++}+else+if+(arr[h]+>=+piv)+{+
++++++++++++h--;
++++++++}+else+{+
++++++++++++swap(arr,l,h);
++++++++}
++++}
++++int+idx+=+h;
++++if+(arr[h]+<+piv)+idx%2B%2B;
++++swap(arr,end-1,idx);
++++return+idx;
}
private+static+void+swap(int[]+arr,+int+i,+int+j)+{+
++++int+temp+=+arr[i];
++++arr[i]+=+arr[j];
++++arr[j]+=+temp;
}

public+static+void+main(String...+args)+throws+Exception+{
++++Random+r+=+new+Random(1);
++++int+SIZE+=+1000000;
++++int+N+=+100;
++++int[]+arr+=+new+int[SIZE];
++++int[]+millisRecursive+=+new+int[N];
++++int[]+millisIterative+=+new+int[N];
++++for+(int+t+=+0;+t+<+N;+t%2B%2B)+{+
++++++++for+(int+i+=+0;+i+<+SIZE;+i%2B%2B)+{+
++++++++++++arr[i]+=+r.nextInt(SIZE);
++++++++}
++++++++int[]+tempArr+=+Arrays.copyOf(arr,+arr.length);
++++++++
++++++++long+start+=+System.currentTimeMillis();
++++++++iterativeQsort(tempArr);
++++++++millisIterative[t]+=+(int)(System.currentTimeMillis()-start);
++++++++
++++++++tempArr+=+Arrays.copyOf(arr,+arr.length);
++++++++
++++++++start+=+System.currentTimeMillis();
++++++++recursvieQsort(tempArr,0,arr.length);
++++++++millisRecursive[t]+=+(int)(System.currentTimeMillis()-start);
++++}
++++int+sum+=+0;
++++for+(int+x+:+millisRecursive)+{
++++++++System.out.println(x);
++++++++sum+%2B=+x;
++++}
++++System.out.println("end+of+recursive.+AVG+=+"+%2B+((double)sum)/millisRecursive.length);
++++sum+=+0;
++++for+(int+x+:+millisIterative)+{
++++++++System.out.println(x);
++++++++sum+%2B=+x;
++++}
++++System.out.println("end+of+iterative.+AVG+=+"+%2B+((double)sum)/millisIterative.length);
}|code-block|syntax|javascript|3069097|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test|1|https://en.wikipedia.org/wiki/P-value^0|D|9|0|0|0|B|8|O|6|0|0|0|3|0|15|N|0|0|K|11|1|0|0|7|7|H|3|M|G|0|0|0^^$0|@$1|2|3|4|5|6|7|1E|8|@$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1H|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|1I|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|1J|8|@$9|1K|A|1L|B|L]|$9|1M|A|1N|B|L]]|D|@]|E|$]]|$1|M|3|-4|5|6|7|1O|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|1P|8|@$9|1Q|A|1R|B|C]]|D|@]|E|$]]|$1|P|3|Q|5|6|7|1S|8|@]|D|@$9|1T|A|1U|1|1V]]|E|$]]|$1|R|3|S|5|6|7|1W|8|@]|D|@$9|1X|A|1Y|1|1Z]]|E|$]]|$1|T|3|U|5|6|7|20|8|@]|D|@]|E|$]]|$1|V|3|W|5|6|7|21|8|@$9|22|A|23|B|L]|$9|24|A|25|B|L]|$9|26|A|27|B|L]]|D|@]|E|$]]|$1|X|3|Y|5|6|7|28|8|@]|D|@]|E|$]]|$1|Z|3|10|5|11|7|29|8|@]|D|@]|E|$12|13]]|$1|14|3|-4|5|6|7|2A|8|@]|D|@]|E|$]]]|15|$16|$5|17|18|19|E|$1A|1B]]|1C|$5|17|18|19|E|$1A|1D]]]]

In terms of (asymptotic) time complexity - they are both the same.
&quot;Recursive is slower then iterative&quot; - the rational behind this statement is because of the overhead of the recursive stack (saving and restoring the environment between calls).
 However -these are constant number of ops, while not changing the number of &quot;iterations&quot;.
Both recursive and iterative quicksort are <code>O(nlogn)</code> average case and <code>O(n^2)</code> worst case.
<hr />
EDIT:
just for the fun of it I ran a benchmark with the (java) code attached to the post , and then I ran <a href="http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test" rel="nofollow noreferrer">wilcoxon statistic test</a>, to check what is the probability that the running times are indeed distinct
The results may be conclusive (P_VALUE=2.6e-34, <a href="https://en.wikipedia.org/wiki/P-value" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/P-value</a>. Remember that the P_VALUE is P(T &gt;= t | H) where T is the test statistic and H is the null hypothesis). But the answer is not what you expected.
 The average of the iterative solution was 408.86 ms while of recursive was 236.81 ms
(Note - I used <code>Integer</code> and not <code>int</code> as argument to <code>recursiveQsort()</code> - otherwise the recursive would have achieved much better, because it doesn't have to box a lot of integers, which is also time consuming - I did it because the iterative solution has no choice but doing so.
Thus - your assumption is not true, the recursive solution is faster (for my machine and java for the very least) than the iterative one with P_VALUE=2.6e-34.
<pre class="lang-java prettyprint-override"><code>public static void recursiveQsort(int[] arr,Integer start, Integer end) { 
 if (end - start &lt; 2) return; //stop clause
 int p = start + ((end-start)/2);
 p = partition(arr,p,start,end);
 recursiveQsort(arr, start, p);
 recursiveQsort(arr, p+1, end);

}

public static void iterativeQsort(int[] arr) { 
 Stack&lt;Integer&gt; stack = new Stack&lt;Integer&gt;();
 stack.push(0);
 stack.push(arr.length);
 while (!stack.isEmpty()) {
 int end = stack.pop();
 int start = stack.pop();
 if (end - start &lt; 2) continue;
 int p = start + ((end-start)/2);
 p = partition(arr,p,start,end);

 stack.push(p+1);
 stack.push(end);

 stack.push(start);
 stack.push(p);

 }
}

private static int partition(int[] arr, int p, int start, int end) {
 int l = start;
 int h = end - 2;
 int piv = arr[p];
 swap(arr,p,end-1);

 while (l &lt; h) {
 if (arr[l] &lt; piv) {
 l++;
 } else if (arr[h] &gt;= piv) { 
 h--;
 } else { 
 swap(arr,l,h);
 }
 }
 int idx = h;
 if (arr[h] &lt; piv) idx++;
 swap(arr,end-1,idx);
 return idx;
}
private static void swap(int[] arr, int i, int j) { 
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
}

public static void main(String... args) throws Exception {
 Random r = new Random(1);
 int SIZE = 1000000;
 int N = 100;
 int[] arr = new int[SIZE];
 int[] millisRecursive = new int[N];
 int[] millisIterative = new int[N];
 for (int t = 0; t &lt; N; t++) { 
 for (int i = 0; i &lt; SIZE; i++) { 
 arr[i] = r.nextInt(SIZE);
 }
 int[] tempArr = Arrays.copyOf(arr, arr.length);
 
 long start = System.currentTimeMillis();
 iterativeQsort(tempArr);
 millisIterative[t] = (int)(System.currentTimeMillis()-start);
 
 tempArr = Arrays.copyOf(arr, arr.length);
 
 start = System.currentTimeMillis();
 recursvieQsort(tempArr,0,arr.length);
 millisRecursive[t] = (int)(System.currentTimeMillis()-start);
 }
 int sum = 0;
 for (int x : millisRecursive) {
 System.out.println(x);
 sum += x;
 }
 System.out.println(&quot;end of recursive. AVG = &quot; + ((double)sum)/millisRecursive.length);
 sum = 0;
 for (int x : millisIterative) {
 System.out.println(x);
 sum += x;
 }
 System.out.println(&quot;end of iterative. AVG = &quot; + ((double)sum)/millisIterative.length);
}
</code></pre>

blocks|key|3069169|text|这就是我在Javascript中想出的解决方案。我想它起作用了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3069170|​|3069171|function+qs_iter(items)+{
++++if+(!items+%7C%7C+items.length+<=+1)+{
++++++++return+items
++++}
++++var+stack+=+[]
++++var+low+=+0
++++var+high+=+items.length+-+1
++++stack.push([low,+high])
++++while+(stack.length)+{
++++++++var+range+=+stack.pop()
++++++++low+=+range[0]
++++++++high+=+range[1]
++++++++if+(low+<+high)+{
++++++++++++var+pivot+=+Math.floor((low+%2B+high)+/+2)
++++++++++++stack.push([low,+pivot])
++++++++++++stack.push([pivot%2B1,+high])
++++++++++++while+(low+<+high)+{
++++++++++++++++while+(low+<+pivot+&&+items[low]+<=+items[pivot])+low%2B%2B
++++++++++++++++while+(high+>+pivot+&&+items[high]+>+items[pivot])+high--
++++++++++++++++if+(low+<+high)+{
++++++++++++++++++++var+tmp+=+items[low]
++++++++++++++++++++items[low]+=+items[high]
++++++++++++++++++++items[high]+=+tmp
++++++++++++++++}
++++++++++++}
++++++++}
++++}
++++return+items
}|code-block|syntax|javascript|3069172|3069173|如果发现错误，请告诉我:)|3069174|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|P|8|@]|9|@]|A|$G|H]]|$1|I|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|R|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|M|$]]

That's the solution i came up with in Javascript. I think it works.

<code>

<pre><code>function qs_iter(items) {
 if (!items || items.length &lt;= 1) {
 return items
 }
 var stack = []
 var low = 0
 var high = items.length - 1
 stack.push([low, high])
 while (stack.length) {
 var range = stack.pop()
 low = range[0]
 high = range[1]
 if (low &lt; high) {
 var pivot = Math.floor((low + high) / 2)
 stack.push([low, pivot])
 stack.push([pivot+1, high])
 while (low &lt; high) {
 while (low &lt; pivot &amp;&amp; items[low] &lt;= items[pivot]) low++
 while (high &gt; pivot &amp;&amp; items[high] &gt; items[pivot]) high--
 if (low &lt; high) {
 var tmp = items[low]
 items[low] = items[high]
 items[high] = tmp
 }
 }
 }
 }
 return items
}
</code></pre>

</code>

Let me know if you found a mistake :)

I learnt about quick sort and how it can be implemented in both Recursive and Iterative method. 
In Iterative method:

<ol>
<li>Push the range (0...n) into the stack</li>
<li>Partition the given array with a pivot</li>
<li>Pop the top element.</li>
<li>Push the partitions (index range) onto a stack if the range has more than one element</li>
<li>Do the above 3 steps, till the stack is empty</li>
</ol>

And the recursive version is the normal one defined in wiki.

I learnt that recursive algorithms are always slower than their iterative counterpart. 
So, Which method is preferred in terms of time complexity (memory is not a concern)? 
Which one is fast enough to use in Programming contest? 
Is c++ STL sort() using a recursive approach?

Quicksort: Iterative or Recursive

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我学习了快速排序，以及如何在递归和迭代方法中实现它。在迭代方法中：将范围(0...n)推入带有枢轴的给定数组中弹出顶部元素。如果范围有多个元素，则将分区(索引范围)推入堆栈执行上述3个步骤，直到堆栈为空<代码>G211</代码>递归版本是在wiki中定义的普通版本。我了解到递归算法总是比它们的迭代算法慢。那么，在时间复...

问快速排序:迭代或递归
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问快速排序:迭代或递归EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问快速排序:迭代或递归
EN