就（渐近）时间复杂度而言，它们都是相同的。
“递归慢于迭代” –该语句背后的原因是由于递归堆栈的开销（在两次调用之间保存和恢复环境）。
但是-这些是固定数量的操作，而不会更改“迭代”的数量。
递归和迭代快速排序都是
O(nlogn)普通情况 和
O(n^2)最坏情况 。
编辑：
只是为了好玩，我运行了一个基准测试，并在文章中附加了（java）代码，然后运行了wilcoxon统计测试，以检查运行时间确实不同的概率是多少
结果是结论性的（P_VALUE = 2.6e-34，这意味着它们相同的概率是2.6 * 10 ^ -34-非常不可能）。但是答案不是您所期望的。
迭代解决方案的平均值为408.86 ms，而递归解决方案的平均值为236.81 ms
（注意-我使用了-
Integer而不是
int作为参数
recursiveQsort()-否则递归会取得更好的效果，因为它不必装很多整数，这也很费时-
我这样做是因为迭代解决方案别无选择，这样做。
因此-您的假设是不正确的，递归解决方案比P_VALUE = 2.6e-34的迭代解决方案要快（至少对我的机器和Java而言）。
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);}
