具有 2 种分区的快速排序

Question

我正在尝试通过 Sadgewick 实现 quicksort 算法。代码取自这里 http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

这是书中的内容：

void quicksort(Item a[], int l, int r)
{ 
   int i = l-1, j = r; Item v = a[r];

   if (r <= l) return;

   for (;;)
   {
      while (a[++i] < v) ;

      while (v < a[--j]) if (j == l) break;

      if (i >= j) break;

      exch(a[i], a[j]);
   }

   exch(a[i], a[r]);
   quicksort(a, l, i-1);
   quicksort(a, i+1, r);
}

这是我在 C# 中的实现：

static void QuickSort2Partitions(int[] a, int left, int right)
{
    int i = left - 1, j = right;
    var v = a[right];

    if (right <= left)
        return;

    while(true)
    {
        while (a[++i] < v) ;
        while(v < a[--j])
        {
            if (j == left)
                break;
        }
        if (i >= j)
            break;

        var c1 = a[i];
        a[i] = a[j];
        a[j] = c1;
    }

    var c2 = a[i];
    a[i] = a[right];
    a[right] = c2;

    QuickSort2Partitions(a, left, i - 1);
    QuickSort2Partitions(a, i + 1, right);
}

我试着这样称呼它：

var a = new int[10] { 9, 4, 5, 3, 1, 2, 8, 7, 6, 0 };
QuickSort2Partitions(a, 0, a.Length - 1);

但是对于第一个递归调用，它将 -1 作为 right 传递并且此代码抛出 out of range exception:

var v = a[right];

自 right is -1。如果我在调试中更改为 0，则进程继续并以正确的输出结束。

我是不是漏掉了什么？

Answer 1

只需拨打

var v = a[right];

行后

if (right <= left)
    return;

具有 2 种分区的快速排序

Quicksort with 2 way partitioning

c#

algorithm

quicksort