我的快速排序实现有问题

Question

新手程序员在这里试图实现快速排序，但它不会工作。我已经查看了在线资源，但我似乎无法发现我的实现中的错误。提前谢谢。

EDIT问题我似乎在快速排序函数中卡住了，程序只是挂起了。当我尝试用printf's调试它时，原始数组似乎已经被修改为意外数字(不是来自原始列表)，例如0。

void quicksort(int a[], const int start, const int end)
{
   if( (end - start + 1 ) < 2)
      return;
   int pivot = a[rand()%(end - start)];
   //Two pointers
   int L = start;
   int R = end;
   while(L < R)
   {
      while(a[L] < pivot)
         L++;
      while(a[R] > pivot)
         R--;
      if(L < R)
         swap(a,L,R);      
   }
   quicksort(a, start, L-1);
   quicksort(a, L+1, end );
}
void swap(int a[], const int pos1, const int pos2)
{
   a[pos1] ^= a[pos2];
   a[pos2] ^= a[pos1];
   a[pos1] ^= a[pos2];
}
int main()
{
   int array[20] = {0};
   int size = sizeof(array)/sizeof(array[0]);//index range = size - 1
   int i = 0;
   printf("Original: ");
   for (i; i < size; i++)
   {
      array[i] = rand()%100+ 1;
      printf("%d ", array[i]);
   }
   printf("n");
   quicksort(array,0,size-1);
   int j = 0;
   printf("Sorted: ");
   for(j; j < size; j++)
      printf("%d ", array[j]);
   printf("n");
}

附加问题:关于调用快速排序递归，左和右指针总是指向每个分区结束的枢轴吗?如果是这样，从开始到L-1和L+1到结束调用快速排序是否正确?

if (L <R)在交换必要之前?>

Answer 1

我认为问题源于逻辑上的两个错误。第一个在这里:

int pivot = a[rand()%(end - start)];

请注意，它总是选择[0,end - start]范围内的枢轴，而不是[start, end]。我想你应该有一些像

int pivot = a[rand()%(end - start) + start];

让你在你想要的范围内选择一个枢轴。

另一个错误在这个循环代码中:

while(L < R)
{
   while(a[L] < pivot)
      L++;
   while(a[R] > pivot)
      R--;
    if(L < R)
      swap(a,L,R);      
}

假设L < R，但a[L]、a[R]、pivot都是相同的值。例如，如果您对包含重复元素的范围进行快速排序，可能会出现这种情况。当您将rand与rand的标准Linux实现一起使用时，也会出现这种情况(我在我的机器上尝试过，27重复了两次)。如果是这种情况，那么你永远不会移动L或R，因为循环中的条件总是求值为false。当可能存在重复时，您需要更新分区元素的逻辑，否则您将进入无限循环。

希望这对你有帮助!

Answer 2

While语句之后，R应该小于L，试试这个:

quicksort(a, start, R);
quicksort(a, L, end ); 

语句if(L < R)是不必要的