快速排序:迭代或递归 [英] Quicksort : Iterative or Recursive
问题描述
我了解快速排序,以及它如何在这两个递归与迭代的方法来实现。
在迭代的方法:
I learnt about quick sort and how it can be implemented in both Recursive and Iterative method.
In Iterative method :
- 按范围(0 ... n)的入堆栈
- 在分区中的给定阵列枢轴
- 在弹出的顶级元素。
- 推分区(指数范围)堆叠成如果范围包含多个元素
- 请在上述3个步骤,直到堆栈为空
和递归版本是正常的维基定义。
And the recursive version is the normal one defined in wiki.
我了解到,递归算法总是比自己的迭代对手慢。
所以,这是方法pferred的时间复杂度(内存是不是一个问题)$ P $?
哪一个是速度不够快编程大赛使用?
是C ++ STL的sort()使用递归的方法呢?
I learnt that recursive algorithms are always slower than their Iterative counterpart.
So, Which is 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() uses 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)code attahced到后一个标杆,然后我跑的秩统计检验,要检查什么的概率是运行时间的确是不同的。
just for the fun of it I ran a benchmark with the (java) code attahced 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.6E-34,这意味着,它们是相同的概率是2.6 * 10 ^ -34 - 非常不可能)。但答案是不是你所期望的。
迭代求解的平均值为408.86毫秒递归,同时为236.81毫秒
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 recursvieQsort(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);
recursvieQsort(arr, start, p);
recursvieQsort(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);
}
这篇关于快速排序:迭代或递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!