地狱的C代码:快速排序程序运行到无限循环:奇怪的情况

Question

我已经为快速排序写了一个C代码，看起来很好。但是代码不能完美地工作，并且在从数组中获取值时奇怪地进入无限循环或其他东西(我不知道)，并且在循环后不做任何事情。

#include<stdio.h>
int flag=0;
int partition(int *,int,int);
void quicksort(int *A,int low, int high)          //Code for quicksort function
{
    int pivot;
    printf("%d",flag);
    flag++;
    if(low<high)
    {
     pivot =partition(A,low,high);        //calls partition function
     quicksort(A,low,pivot);
     quicksort(A,pivot,high);
    }
}
//code for partition function
int partition(int *A,int low,int high)
{
    int pivot,left,right,temp;
    pivot=A[low];
    left=low;
    right=high;
    printf("%d",flag);
    flag++;
    while(left<right)
        {
         while(A[left]<pivot)
            left++;
         while(A[right]>pivot)
            right++;
         if(left<right)
            {
             temp=A[left];
             A[left]=A[right];
             A[right]=temp;
            }
        }
    temp=A[right];
    A[right]=A[left];
    A[left]=temp;
    return right;
}
int main()
    {
        int a[10],i,n;
        printf("n***QUICK SORT***");
        printf("nENTER THE NUMBERS OF ENTRIES:");
        scanf("%d",&n);
        printf("nENTER THE ENTRTIES IN ARRAY:");
        //PROBLEM IS IN THIS LOOP OR ELSE (I DONT KNOW WHAT EXACTLY WHAT THE PROBLEM IS)
        for(i=0;i<n;i++)
        {
            printf("i=%dn",i);
            scanf("%d",&a[i]);     
        }
        //IF WE COMMENT THIS BELOW LINE OF FUNCTION CALL THEN LOOP WORKS FINE
        quicksort(a,0,n-1);    //passes the array and first and last element
        printf("nTHE SORTED ARRAY IS:n");
        for(i=0;i<n;i++)
            printf(" %d n ",a[i]);
        return 0;
    }

Answer 1

正如许多人已经在您的代码注释中指出的那样。您需要重新考虑快速排序算法的分区步骤—您遇到无限循环的原因是由于在交换之后，left和right从未更新，导致无限循环。

这不是我自己的，但在我学习复杂排序算法时帮助了我:

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  /* partition */
  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
  };

您可能会发现这很有帮助，正如许多人所说，您可能需要清理代码以帮助调试方面。

Answer 2

似乎 right++;应该是right--;

Answer 3

在你的函数quicksort()

quicksort(A,low,pivot);
quicksort(A,pivot,high);

这些参数应该像这样-

quicksort(A,low,pivot-1);  
quicksort(A,pivot+1,high);

函数partition()

     while(A[right]>pivot)
        right++;

在这个循环中，right应该递减

    while(A[right]>pivot)
        right--;

最后是这个函数的交换

 temp=A[right];
 A[right]=A[left];
 A[left]=temp;

但是实际上right应该是pivot

的最后一个位置

 A[left]=A[right]
 A[right]=pivot

和只是一个建议，请增加你的数组a[]的大小在main函数

Answer 4

正如许多评论者已经指出的那样，这段代码中有很多问题，我只是想给你一个实际工作的实现，包括(希望)对所做的事情有帮助的评论:

#include <stdio.h>       
#include <stdlib.h>
#define CHUNK_SIZE 16
static void quicksort_rec(int *l, int *r)
{
    int *p, *ll, *rr, t;
    if (r-l < 1) return; /* only one element left -> nothing to sort */
    p = r;      /* use last element for pivot (any element would do) */
    rr = r-1;   /* pointer to last element to compare with pivot */
    ll = l;     /* pointer to first element to compare with pivot */
    while (1)
    {
        /* move ll until we find something greater than pivot on the left */
        while (ll <= rr && *ll <= *p) ++ll;
        /* move rr until we find something smaller than pivot on the right */
        while (ll <= rr && *rr >= *p) --rr;
        /* ll and rr met? then we're done with this step */
        if (rr <= ll)
        {
            /* swap pivot to the "meeting position" */
            t = *p;
            *p = *ll;
            *ll = t;
            /* sort partitions recursively */
            quicksort_rec(l, ll-1);
            quicksort_rec(ll+1, r);
            /* done */
            return;
        }
        /* swap greater element on the left with smaller element on the right */
        t = *rr;
        *rr = *ll;
        *ll = t;
    }
}
static void quicksort(int *v, int num)
{
    quicksort_rec(v, v+num-1);
}

int main()
{
    char buf[64];       /* buffer for user input */
    int *values;        /* pointer to dynamically allocated array */
    int avail;          /* number of currently free slots in the array */
    int entries = 0;    /* number of total entries in the array */
    int i;              /* iterating variable */
    puts("Quicksort Examplen"
         "=================n"
         "n"
         "Enter whole numbers to sort, just hitting enter starts sorting.n");
    /* allocate first chunk of memory */
    values = malloc(CHUNK_SIZE * sizeof(int));
    if (!values)
    {
        perror("malloc");
        exit(1);
    }
    avail = CHUNK_SIZE;
    while (1)
    {
        fputs("Please enter next number: ", stdout);
        /* try reading user input, if impossible, break */
        if (!fgets(buf, 64, stdin)) break;
        /* if input is empty, break */
        if (buf[0] == '' || buf[0] == 'r' || buf[0] == 'n') break;
        /* convert input to integer as next value for array */
        values[entries] = atoi(buf);
        printf("Added `%d' to sort listn", values[entries]);
        ++entries;
        /* check whether there is space left in the array */
        if (!--avail)
        {
            /* if not, increase array size by the next chunk */
            values = realloc(values, (entries + CHUNK_SIZE) * sizeof(int));
            if (!values)
            {
                perror("realloc");
                exit(1);
            }
            /* reset available slots to size of chunk */
            avail = CHUNK_SIZE;
        }
    }
    printf("Now sorting %d elements with quicksort.n", entries);
    /* sort the array */
    quicksort(values, entries);
    puts("Result:");
    for (i = 0; i < entries; ++i)
    {
        printf("%dn", values[i]);
    }
    free(values);
    return 0;
}