c - 快速排序效果不佳

Question

我曾尝试使用一本书中的伪代码(看起来像维基百科中的伪代码)来实现快速排序，但我无法让它工作。

此源代码:

int partitionare(int a[], int n, int p, int r)
{
   int x, i, j, aux;
   x = a[r]; // pivot
   i = p - 1;
   for (j = p; j < r; j++)
   {
       if (a[j] <= x)
       {
           i++;
           aux = a[j];
           a[j] = a[i];
           a[i] = aux;
        }   
   }
   aux = a[i + 1];
   a[i + 1] = a[r];
   a[r] = aux;
   return i + 1;
}
void quicksort(int a[], int n, int p, int r)
{
    if (p < r)
    {
       int q = partitionare(a, n, p, r);
       partitionare(a, n, p, q - 1);
       partitionare(a, n, q + 1, r);
    }
}

其中 p 和 r 是数组的开头和结尾

调用函数:

quicksort(a, n, 0, n-1);

不要介意第二个参数 n。这仅用于测试目的。

Answer 1

根据Wikipedia article函数 quicksort() 中的最后一次调用是递归地调用自身(而不是函数 partition())

void quicksort(int a[], int n, int p, int r)
{
    if (p < r)
    {
       int q = partitionare(a, n, p, r);
       partitionare(a, n, p, q - 1);     /* recursive quicksort() here */
       partitionare(a, n, q + 1, r);     /* recursive quicksort() here */
    }
}