c - 无法在快速排序中正确传递数组

Question

这是我的程序，它正在编译和运行，没有语法错误。但是它没有对数组进行排序。问题在于我在函数中传递数组的位置

#include<stdio.h>
#include<string.h>
int partition (int *,int,int);
void quicksort (int *,int,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;

length=sizeof(a)/sizeof(a[0]);
quicksort(a,0,length-1);
printf("the sorted array is\n");
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
int partition(int *num,int p,int r)
{
 int x,j,i,temp,bak;
  x=num[r];
  i=p-1;
       for(j=0;j<=r-1;j++)
  { 
         if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;


      {
       printf(" %d",num[bak]);
        }

     }  
  }
  num[i+1]=num[r];

 return i+1;
}

void quicksort (int *num,int p,int r)
{ 
 int q;
 if (p<r)
  {
    call++;

    q=partition(num,p,r);
        quicksort(num,p,q-1);
        quicksort(num,q+1,r);
  }
}    

上述在函数中传递数组的方式正是我想知道的，因为这给函数分区带来了问题。

当交换发生时在函数分区内然后我尝试在那里打印数组本身(它不是排序数组但只是为了看看事情到达了什么点)然后我看到我传递的数组中只有 2 或 3 个元素是正在打印并且数组的其余部分丢失了一些地方。所以我怀疑数组没有正确传递。

为了能够看到在函数中传递数组的问题是什么，我编写了一个较小的程序 ka1.c

#include<stdio.h>
void pass(int *);
int main ()
{
int a[]={3,5,61,32,12};
pass(a);
}
void pass (int *num)
{
int i,j;
 j=sizeof(num)/sizeof(num[0]);
 for (i=0;i<j;i++)
 printf(" %d",num[i]);
}

现在，当我运行上面的代码时，我只得到输出

 3 5

我期待完整的数组打印在 ka1.c 的输出中。好像你注意到数组的其余部分没有被打印出来。那去哪儿了？ 我在快速排序中也使用了相同的逻辑，因此我觉得两种情况下的错误是相同的。

更新1
在下面的评论之后，我通过

检查了在 quicsort.c 分区函数中收到的数组长度

sizeof(num)/sizeof(num[0]);

找到原始数组

int a[]={81, 12, 90, 3, 49, 108, 47};

当我在函数分区中传递它时，这里的长度为 7长度只有2。程序 ka1.c 的情况也是如此 那么为什么在这两种情况下只有长度为 2？

更新2
作为下面给出的建议，我也传递了长度

#include<stdio.h>
#include<string.h>
int partition (int *,int,int,int);
void quicksort (int *,int,int,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;
printf("the sorted array is\n");
length=sizeof(a)/sizeof(a[0]);
printf("length of array %d\n",length);
printf("quick sort called in main\n");
quicksort(a,0,length-1,length);
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
int partition(int *num,int p,int r,int june)
{
 int x,j,i,temp,bak,length;
  x=num[r];
  i=p-1;
  bak=0;
  printf("inside the partition\n");
 printf("length of june recieved =%d \n",june);
  for(j=0;j<=r-1;j++)
  { 
    if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;
    printf("printing array after swap\n");
      for(;bak<7;bak++)
      {
           printf(" %d ",num[bak]);
          }
     }  
  }
  num[i+1]=num[r];

 return i+1;
}

void quicksort (int *num,int p,int r,int june)
{ 
 int q,bbc,ccd;
 if (p<r)
  {
    call++;
         printf("partition called  %d times p=%d r=%d\n",call,p,r);
    printf("before sending to function length of june=%d \n",june);
    q=partition(num,p,r,june);
    bbc=q-1-p+1;
        quicksort(num,p,q-1,bbc);
        ccd=r-q-1+1;
        quicksort(num,q+1,r,ccd);
  }
}

但是程序仍然无法打印排序后的数组。您可以编译并运行上面的代码。

已解决
最后在下面回复的帮助下，我已经能够解决上述问题。语句中函数分区的错误

  for (j = 0; j <= r - 1; j++)

应该是

  for (j = p; j <= r - 1; j++)

注意 j=p 和 j=0这里

j=0

是错误的，因为当尝试对第二个分区进行递归排序时，它开始干扰第一个分区，因此结果也是错误的。

在这个程序中，我在使用 gdb 调试递归函数时遇到了问题。请查看this thread还调试递归非常棘手。

所以正确的代码是

#include<stdio.h>
#include<string.h>
int partition (int *, int, int, int);
void quicksort (int *, int, int, int);
static int call = 0;
int
main ()
{
  int i, j, choice;
  int length;
  int a[] = { 81, 12, 90, 3, 49, 108, 47 };
  i = 0;
  printf ("the sorted array is\n");
  length = sizeof (a) / sizeof (a[0]);
  printf ("length of array %d\n", length);
  printf ("quick sort called in main\n");
  quicksort (a, 0, length - 1, length);
  for (i = 0; i < length; i++)
    printf (" %d ", a[i]);
}

int
partition (int *num, int p, int r, int june)
{
  int x, j, i, temp, bak, length;
  x = num[r];
  i = p - 1;
  bak = 0;
  for (j = p; j <= r - 1; j++)
    {
      if (num[j] <= x)
    {
      i = i + 1;
      temp = num[i];
      num[i] = num[j];
      num[j] = temp;
    }
    }
  temp=num[i+1];
  num[i + 1] = num[r];
  num[r]=temp;
  return i + 1;
}

void
quicksort (int *num, int p, int r, int june)
{
  int q, bbc, ccd;
  if (p < r)
    {
      call++;
      q = partition (num, p, r, june);
      bbc = q - 1 - p + 1;
      quicksort (num, p, q - 1, bbc);
     ccd=r-q+1;
      quicksort (num, q + 1, r, ccd);
    }
}

Answer 1

问题在于您计算数组长度的方式......尝试简单地将数组中的元素数量作为快速排序方法的参数......我想你会有正确答案...我也同意所提出的观点......尝试将数组的长度与数组一起传递......尝试两者并告诉我哪个有效......:)新代码:

#include<stdio.h>
#include<string.h>
//int partition (int *,int,int);
void q_sort(int*,int,int);
void quicksort (int *,int);
static int call=0;
int main()
{
int i,j,choice;
int length;
int a[]={81, 12, 90, 3, 49, 108, 47};
i=0;
printf("the sorted array is\n");
length=sizeof(a)/sizeof(a[0]);
printf("length of array %d\n",length);
printf("quick sort called in main\n");
quicksort(a,length);
for(i=0;i<length;i++)
 printf (" %d ",a[i]);
}
/*int partition(int *num,int p,int r)
{
 int x,j,i,temp,bak,length;
  x=num[r];
  i=-1;
  bak=0;
  printf("inside the partition\n");
  for(j=0;j<=r-1;j++)
  {
    if(num[j]<=x)
     {
      i=i+1;
       temp=num[i];
       num[i]=num[j];
       num[j]=temp;
    printf("printing array after swap\n");
      for(;bak<7;bak++)
      {
           printf(" %d ",num[bak]);
          }
     }
  }
  num[i+1]=num[r];

 return i+1;
}
*/
/*void quicksort (int *num,int p,int r)
{
 int q,bbc,ccd;
 if (p<r)
  {
    call++;
         printf("partition called  %d times p=%d r=%d\n",call,p,r);
    q=partition(num,p,r);
    bbc=q-1-p+1;
        quicksort(num,p,q-1);
        ccd=r-q-1+1;
        quicksort(num,q+1,r);
  }
}*/
void quicksort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}