c - 我的快速排序实现有问题

Question

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

编辑 我遇到的问题似乎卡在快速排序函数中，程序挂起。当我尝试用 printf 调试它时，原始数组似乎被修改为意外数字(不是来自原始列表)，例如 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");
}

附加问题:关于递归调用快速排序，左右指针是否始终指向每个分区末尾的枢轴？如果是这样，调用从 start 到 L-1 和 L+1 到 end 的快速排序是否正确？

另外，交换前的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，因为循环中的条件总是计算为假。当可能出现重复时，您将需要更新分区元素的逻辑，否则您将在此处进入无限循环。

希望这对您有所帮助!