相关疑难解决方法(0)

在邮件列表和在线讨论中经常出现的主题之一是进行计算机科学学位的优点(或缺乏).似乎一次又一次地为负面派对提出的论点是,他们已编码了若干年,他们从未使用过递归.

所以问题是:

1. 什么是递归？
2. 我什么时候使用递归？
3. 为什么人们不使用递归？

在算法简介中, p169它讨论了使用尾递归Quicksort.

本章前面的原始Quicksort算法是(伪代码)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

使用尾递归的优化版本如下

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

在哪里Partition根据枢轴对阵列进行排序.

不同之处在于第二种算法只调用Quicksort一次来对LHS进行排序.

有人可以向我解释为什么第一个算法可能导致堆栈溢出,而第二个算法不会？或者我误解了这本书.

我试图对QuickSort进行实现(对于小数组,中间值为3分区元素和插入排序),并将其与MergeSort的实现进行比较,但即使QuickSort平均时间应该优于MergeSort,每次我执行它,似乎需要更多的时间来排序一个数组(即使是一个随机顺序).知道为什么会这样吗？

快速排序:

public class Quick {

    private static final int M = 10;
    private static Random random = new Random();

    public void sort(int[] a) {
        sort(a, 0, a.length - 1);
        insertionSort(a, 0, a.length - 1);
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi - lo <= 10) return;
        swap(a, lo, pivot(a, lo, hi));
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo;
        while (i <= gt) {
            if      (a[i] < …