Quicksort：迭代或递归

本文介绍了Quicksort：迭代或递归的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我学习了快速排序以及如何在递归和迭代方法中实现它。 在迭代方法中：

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

将范围（0 ... n）推入堆栈

使用数据透视表对给定数组进行分区

弹出顶部元素。

如果范围有多个元素，则将分区（索引范围）推入堆栈

执行上述3个步骤，直到堆栈是空的

Push the range (0...n) into the stack

Partition the given array with a pivot

Pop the top element.

Push the partitions (index range) onto a stack if the range has more than one element

Do the above 3 steps, till the stack is empty

递归版本是wiki中定义的正常版本。

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

我了解到递归算法总是慢于它们的迭代算法。 那么，就时间复杂度而言，哪种方法更受欢迎（内存不是问题）？ 在编程竞赛中哪一个足够快？ 使用递归方法c ++ STL sort（）？

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?

推荐答案

就（渐近）时间复杂度而言 - 它们都是相同的。

递归慢于迭代 - 这个语句背后的理性是由于递归堆栈的开销（在调用之间保存和恢复环境）。 但是 - 这些是操作的常数，而不是改变迭代次数。

"Recursive is slower then iterative" - 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 "iterations".

递归和迭代快速排序都是 O（nlogn） 平均情况和 O（n ^ 2） 最坏情况。

Both recursive and iterative quicksort are O(nlogn) average case and O(n^2) worst case.

编辑：

只是为了它的乐趣我运行了附加到帖子的（java）代码的基准测试，然后我运行了 wilcoxon统计测试，检查运行时间确实不同的概率

just for the fun of it I ran a benchmark with the (java) code attached to the post , and then I ran wilcoxon statistic test, to check what is the probability that the running times are indeed distinct

结果是确定的（P_VALUE = 2.6 e-34，这意味着它们相同的概率是2.6 * 10 ^ -34 - 非常不可能）。但答案不是你所期望的。 迭代解的平均值是408.86 ms，而递归的平均值是236.81 ms

The results are conclusive (P_VALUE=2.6e-34, that means that the probability they are the same is 2.6*10^-34 - very not probable). 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

（注意 - 我用整数而不是 int 作为的参数recursiveQsort（） - 否则递归会更好，因为它不需要包含很多整数，这也很耗时 - 我这样做是因为迭代解决方案别无选择，只能这样做。

(Note - I used Integer and not int as argument to recursiveQsort() - 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.

因此 - 你的假设不正确，递归解决方案更快（对于我的机器和java至少）然后是迭代的P_VALUE = 2.6e-34。

Thus - your assumption is not true, the recursive solution is faster (for my machine and java for the very least) then the iterative one with P_VALUE=2.6e-34.

public static void recursiveQsort(int[] arr,Integer start, Integer end) { if (end - start < 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<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 + ((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 < h) { if (arr[l] < piv) { l++; } else if (arr[h] >= piv) { h--; } else { swap(arr,l,h); } } int idx = h; if (arr[h] < 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 < N; t++) { for (int i = 0; i < 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("end of recursive. AVG = " + ((double)sum)/millisRecursive.length); sum = 0; for (int x : millisIterative) { System.out.println(x); sum += x; } System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length); }