c -在实现快速排序的同时获取分段故障

Question

我想实现堆排序。为此，我阅读了这个http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L06-QuickSort.htm#basic教程，并编写了以下代码:

#include <stdio.h>

int quick_sort(int a[],int first,int last);
int main()
{
    int a[]= {12,3,4,23,1,7,9,34,89,45};
    int i;
    printf("Enter 10 integers: n");
    for ( i = 0 ; i < 10 ; i++ )
    {
        scanf("%d",&a[i]);
        printf("t%dn",a[i]);
    }
    for ( i = 0 ; i < 10 ; i++ )
    {
        printf("n%d ",a[i]);
    }
    quick_sort(a,0,9);
    for ( i = 0 ; i < 10 ; i++ )
    {
        printf("%d ",a[i]);
    }
    return 0;
}
int quick_sort(int a[],int first,int last)
{
    int i,j,pivot,temp ;
    if ( first - last <= 1 && first - last >= -1 )
    {
        return 0;
    }
    else
    {
        i = first ;
        j = last ;
        pivot = a[(i+j) / 2 ] ;
        while ( i != j )
        {
            while ( a[i] < pivot )
            {
                i++;
            }
            while( a[j] > pivot )
            {
                j--;
            }
            temp = a[i] ;
            a[i] = a[j] ;
            a[j] = temp ;
        }
    }
    quick_sort(a,0,i-1);
    quick_sort(a,j+1,9);
    return 0;
}

在使用gcc编译器运行它时，我得到分段错误。

Answer 1

在问题的quick_sort()函数中有几件事对我来说是一个谜。并不是说他们错了;只是我不明白各种操作的目的。

经过一段时间的工作，这是我的版本:

void quick_sort(int *a, int first, int last)
   {
   int i,j,pivot,temp;
   if(last <= 1)
       return;
   pivot = a[first + last/2];
   j = first + last/2;
   temp = a[first];
   a[first] = a[j];
   a[j] = temp;
   j = first;
   for(i = first+1; i < first+last; i++)
      {   
      if(a[i] < pivot)
         {
         j++;
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
         }
      }
   temp = a[first];    
   a[first] = a[j];
   a[j] = temp;
   quick_sort(a, first, j-first);
   quick_sort(a, j+1, first+last-j-1);
   return;
   }

Answer 2

我会试试:

quick_sort(a,first,i-1);
quick_sort(a,j+1,last);

代替:

quick_sort(a,0,i-1);
quick_sort(a,j+1,9);

它至少允许对大于10个值的列表进行排序....

您还需要在每次更改后检查i != j，所以我认为这在您的代码中也是有问题的。或者至少使用i而不是j, while语句将永远不会结束。