快速排序：迭代还是递归

Question

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

在迭代方法中：

0. 将范围(0...n)压入栈中 1. 使用一个枢轴对给定数组进行分区 2. 弹出栈顶元素 3. 如果范围中有多于一个元素，则将分区（索引范围）推入栈中 4. 重复上述3个步骤，直到栈为空

而递归版本是在维基百科中定义的普通版本。

我了解到递归算法总是比它们的迭代对应物慢。

那么，在时间复杂度方面，哪种方法更受青睐（内存不是问题）？ 哪一种足够快以在编程竞赛中使用？ C++ STL的sort()函数是否使用递归方法？

- sabari

---

你已经自己回答了。递归版本更短更清晰。迭代版本更快，让你模拟递归调用栈。 - Vitaly Olegovitch

但是我的教授说，递归堆栈深度与我们用于存储分区范围的堆栈相同。那么，迭代的方法为什么会显著更快呢？ - sabari

@sabari：你对递归更快的假设是错误的。我进行了统计测试，并编辑了答案，附上了结果。 - amit

你可以使用队列而不是栈来实现快速排序的迭代版本。算法本身并不要求额外存储必须是LIFO（后进先出）。使用栈的方法更类似于常用的递归描述，但这并不是算法固有的一部分。后进先出结构可能会更具有参考局部性，因此它可能更快，因为它更适合缓存。 - Adrian McCarthy

我猜想区别在于堆空间和栈空间。垃圾回收的代价很高。 - Adrian V

Answer 1

就（渐进）时间复杂度而言，它们是相同的。

"递归比迭代慢" - 这种说法的原因是由于递归栈的开销（在调用之间保存和恢复环境）。
然而，这些是常数次操作，不会改变“迭代”的次数。

无论是递归还是迭代快速排序都是O(nlogn) 平均情况和O(n^2) 最坏情况。

---

编辑：

仅仅为了好玩，我运行了附在帖子中的（java）代码的基准测试，然后我进行了Wilcoxon统计检验，以检查运行时间是否确实不同。

结果可能是有决定性的（P_VALUE=2.6e-34，https://en.wikipedia.org/wiki/P-value。请记住，P_VALUE是P（T >= t | H），其中T是测试统计量，H是零假设）。但答案并不是你期望的。
迭代解法的平均值为408.86毫秒，而递归解法的平均值为236.81毫秒。

（注意 - 我使用Integer而不是int作为recursiveQsort()的参数 - 否则递归会表现得更好，因为它不必装箱很多整数，这也很耗时 - 我这样做是因为迭代解法别无选择。）

因此，你的假设是不正确的，在我的机器和Java环境下，递归解决方案比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);
}

- amit

---

你的测试主要展示了栈类如何高效地运行，而不是迭代版本的快速排序算法的效率。你可以使用一个更加静态且自编的栈，例如具有64个元素，并且push和pop操作将会更快。我猜这比递归方法更快！如果你正确实现它，你可以在最坏情况下对2^64个元素进行排序，这在实际应用中已经足够了。 - Argeman

@Argeman：谢谢你的评论。这实际上是基准测试的重点——栈解决方案非常依赖于栈的实现，而调用栈已经为其目的进行了优化，因此递归解决方案不太可能比迭代解决方案更糟糕，除非您花费大量时间为特定目的优化栈（我怀疑差异是否足以值得花时间）。正如我所说，这只是一个“有趣的测试”——答案背后的主要思想仍然是——渐近时间复杂度是相同的。 - amit

PS：打印格式错误（并且不使用Arrays.toString()）是为了适应http://www.fon.hum.uva.nl/Service/Statistics/Wilcoxon_Test.html上Wilcoxon在线计算器所需的输入。 - amit

@amit 你是怎么执行“Wilcoxon符号秩检验”的呢？有用到什么工具吗？ - Geek

我认为应该是 stack.push(p-1);。 - roottraveller

Answer 2

递归并不总是比迭代慢。快速排序就是一个完美的例子。唯一以迭代方式完成此操作的方法是创建堆栈结构。因此，在不使用递归的情况下，必须按照编译器执行的方式进行操作，而且可能会比编译器做得更差。如果不使用递归，还需要进行更多跳转（将值弹出和推入到堆栈中）。

- Hauleth

---

为什么在弹出和推入时必须跳跃？ - Vitaly Olegovitch

如果没有进行内联，你（在大多数情况下）需要调用一些函数，因此它需要调用。 - Hauleth

请确认一下，您是说使用运行时堆栈（递归）比用户创建的堆栈结构更有效吗？@amit，你有什么想法吗？ - Akash Magoon

我认为这种方法效率较低。因为你需要分配足够的堆空间来构建栈（甚至在内存不足时进行重新分配），你需要在某个地方存储位置，你需要检查角落情况（空/满栈）等等。 - Hauleth

很久以前我曾经看到过由于递归调用太多和编译器限制而导致应用程序崩溃的情况，现在还是这样吗？内存方面呢？仅仅因为硬件更好，并不意味着我们不需要关心...只需看看安卓世界，你会看到有多少应用程序和服务正在运行，其中一些是由新手编写的，导致手机崩溃... - Hassan Faghihi

Answer 3

这是我在Javascript中想出来的解决方案。我认为它有效。

const myArr = [33, 103, 3, 726, 200, 984, 198, 764, 9]

document.write('initial order :', JSON.stringify(myArr), '<br><br>')
qs_iter(myArr)
document.write('_Final order :', JSON.stringify(myArr))

function qs_iter(items) {
  if (!items || 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 + high) / 2)
      stack.push([low, pivot])
      stack.push([pivot + 1, high])
      while (low < high) {
        while (low < pivot && items[low] <= items[pivot])   low++
        while (high > pivot && items[high] > items[pivot])  high--
        if (low < high) {
          var tmp     = items[low]
          items[low]  = items[high]
          items[high] = tmp
        }
      }
    }
  }
  return items
}

如果您发现错误，请告诉我 :)

乔乔先生更新：
这段代码只是混合一些很少会导致排序的值，换句话说从不会。

对于那些有疑问的人，我将它放在了片段中。

- Nir M.

---

这段代码只是混合值，可能在极少数情况下会导致排序，换句话说永远不会。对于那些有疑问的人，我将其放在了片段中。 - Mister Jojo

Answer 4

那么，哪种方法更好呢...？

都不是，也就是说两种方法同时使用。根据amit的answer中修改了recursiveQsort函数，它是这样的。

public static void recIterQsort(int[] arr, int start, int end) { 
    while (end - start >= 2) {  // iteratively,
      int p = start + ((end-start)/2);
      p = partition(arr,p,start,end);
      if( p-start < end-p)   // sort shorter part, recursively
      {
          recIterQsort(arr, start, p);
          start = p+1;    // "call" recIterQsort(arr, p+1, end);
      }
      else
      {
          recIterQsort(arr, p+1, end);
          end = p;        // "call" recIterQsort(arr, start, p);
      }
    }
}

递归地对一个部分进行排序后，我们继续通过循环对剩余部分进行排序。这个转换等同于执行尾调用优化，消除了递归调用，即递归函数中的最后一个操作。

首先对较短的部分进行排序，递归的深度保证不会超过log(n)，所以递归不是问题。而且迭代不需要手动进行任何簿记，也没有Stack，所以可以只使用int索引。

- Will Ness