永无止境的快速排序

Question

我尝试对 int64_t 的数组进行快速排序，如下所示：

void quicksort (int64_t *array,size_t size) { 
    int64_t *split;
    size_t i=0;
    size_t j=size-1;
    if (size>1) {
    split=({
      int64_t p=array[0];
      do {
           for (;array[i]<p;i++);
           for (;array[j]>p;j--);
           swap(array[i],array[j]);
      } while (i<j);
      swap(array[i],array[j]);
      swap(array[j],array[size]);
      &(array[j]);
      })-1;
    quicksort(array,j-1);
    quicksort(split+1,size-j);
    }
    return; 
}

这很好，但是，它在第一次分区通过后立即进入无限递归或无限循环。我该如何解决？

Answer 1

您的分区代码看起来很奇怪，至少有一些问题： for (; a[i] < p; i++) 不保证终止。

然后如果 j 是枢轴元素的最终位置，则您的左数组应该按快速排序（数组，j）而不是 j-1 排序。

Answer 2

我无法编译你的代码（我的编译器很旧）。但不应该：

size_t i=0;

改为初始化为 1，因为您有

int64_t p=array[0];  // partition element?

和

for (;array[i]<p;i++);

这可能不是唯一的问题。

永无止境的快速排序

Never-ending quicksort

c

quicksort

infinite-loop

gcc4.9