请务必理解这个Java代码:-)

Question

只是想知道是否有人能够看一下这段代码来实现quicksort算法并回答我几个问题,请:-)

public class Run
{
  /***************************************************************************
   * Quicksort code from Sedgewick 7.1, 7.2.
   **************************************************************************/
  public static void quicksort(double[] a)
  {
    //shuffle(a); // to guard against worst-case
    quicksort(a, 0, a.length - 1, 0);
  }

  static void quicksort(final double[] a, final int left, final int right, final int tdepth)
  {
    if (right <= left)
      return;
    final int i = partition(a, left, right);

    if ((tdepth < 4) && ((i - left) > 1000))
    {
      final Thread t = new Thread()
      {
        public void run()
        {
          quicksort(a, left, i - 1, tdepth + 1);
        }
      };
      t.start();
      quicksort(a, i + 1, right, tdepth + 1);

      try
      {
        t.join();
      }
      catch (InterruptedException e)
      {
        throw new RuntimeException("Cancelled", e);
      }
    } else
    {
      quicksort(a, left, i - 1, tdepth);
      quicksort(a, i + 1, right, tdepth);
    }
  }

  // partition a[left] to a[right], assumes left < right
  private static int partition(double[] a, int left, int right)
  {
    int i = left - 1;
    int j = right;
    while (true)
    {
      while (less(a[++i], a[right]))
        // find item on left to swap
        ; // a[right] acts as sentinel
      while (less(a[right], a[--j]))
        // find item on right to swap
        if (j == left)
          break; // don't go out-of-bounds
      if (i >= j)
        break; // check if pointers cross
      exch(a, i, j); // swap two elements into place
    }
    exch(a, i, right); // swap with partition element
    return i;
  }

  // is x < y ?
  private static boolean less(double x, double y)
  {
    return (x < y);
  }

  // exchange a[i] and a[j]
  private static void exch(double[] a, int i, int j)
  {
    double swap = a[i];
    a[i] = a[j];
    a[j] = swap;
  }

  // shuffle the array a[]
  private static void shuffle(double[] a)
  {
    int N = a.length;
    for (int i = 0; i < N; i++)
    {
      int r = i + (int) (Math.random() * (N - i)); // between i and N-1
      exch(a, i, r);
    }
  }

  // test client
  public static void main(String[] args)
  {
    int N = 5000000; // Integer.parseInt(args[0]);

    // generate N random real numbers between 0 and 1
    long start = System.currentTimeMillis();
    double[] a = new double[N];
    for (int i = 0; i < N; i++)
      a[i] = Math.random();
    long stop = System.currentTimeMillis();
    double elapsed = (stop - start) / 1000.0;
    System.out.println("Generating input:  " + elapsed + " seconds");

    // sort them
    start = System.currentTimeMillis();
    quicksort(a);
    stop = System.currentTimeMillis();
    elapsed = (stop - start) / 1000.0;
    System.out.println("Quicksort:   " + elapsed + " seconds");

  }
}

我的问题是:

1. 变量的目的是tdepth什么？

2. 这被认为是并行快速排序的"正确"实现吗？我问,因为它不使用implements Runnable或extends Thread...

3. 如果还没有,是否可以修改此代码以使用多个线程？通过传递要用作参数的线程数,例如......？

非常感谢,

布赖恩

Answer 1

它用于跟踪递归深度.检查这是否决定是否并行运行.注意当函数并行运行时,它如何传递tdepth + 1(在被调用的quicksort参数中变为tdepth).这是避免太多并行线程的基本方法.

是的,它肯定是在使用另一个线程.代码:

new Thread()
{
  public void run()
  {
    quicksort(a, left, i - 1, tdepth + 1);
  }
};

创建一个匿名内部类(扩展Thread),然后启动它.