c - 如何用C语言用指针实现快速排序？

Question

所以我目前正在将 Java 快速排序程序翻译成 C，但我不确定我是否正确使用了指针。据我所知，我相信我在分区方法中正确使用了它们，或者至少我的语法是正确的——我没有收到任何错误。我是;但是，得到与我的结果相同的数组。我当前的程序是

' 
// quickSort.c
      #include <stdio.h>
      #include <stdlib.h>
      #
      void swap(int *a, int *b);
      void quickSort( int[], int, int);
      int partition( int*, int, int);
      int main(int argc, char *argv[])
      {
        int a[] = {2, 6, 5, 1}; 
        int i;
       // int arrlength = sizeof(a); WRONG
        int arrlength = 4; 
        printf("\n\nUnsorted array is:  ");
        for(i = 0; i < arrlength; ++i)
            printf(" %d ", a[i]);

        //array, 0, length 
        quickSort( a, 0, arrlength);

        printf("\n\nSorted array is:  ");
        for(i = 0; i < arrlength; ++i)
            printf(" %d ", a[i]);
        printf("\n\n");

      }


      // char yo[] = "Hello"; 
      // &yo[0] = will be equivalent to = Hello &yo[0] points to variable yo[0]

      //array, Leftmost position, Rightmost position
      void quickSort( int a[], int L, int R)
      {
         int k;

         if( R <= L){
          return;
         }
          k = partition( a, L, R);
          quickSort( a, L, k); // Sort left half of partitioned array
          quickSort( a, k+1, R);  // Sort right half of partitioned array
      }




      // L= leftmost position in the array 
      // R= rightmost position in the array 
      // int *a = pointer to array we are sorting 

      int partition(int a[], int L, int R) {

       // [2   , 6 , 5 , 1] 
       //  |             |
       //  |             |   once the two pointers cross we exist the while loop. 
       //  |             |
       //  S             B=4 & p[B]=1

      int pivot; 
      int help; 
      int S; 
      int B; 
      S = L;  //S = current Leftmost position
      B = R-1;//B = rightmost position
      pivot = a[R-1];     //rightmost number in array
      int *pop; 
      pop = &a[B]; //pop points to address of array 
      //*pop is the actual variable in the address a[B]

      while(B > S) {//as long as the two pointers don't cross you continue
        if(a[B-1] > pivot){   //move to the right of the pivot 
          pop = &a[B-1]; 
          B--; 
        }
        else {
          swap(&a[B-1], &a[S]);// move to left of the pivot 
          S++; 
        }
      }

        pop = &pivot;  // Put pivot in the "hole" 
        return B;  //return the position of the pivot

      }

      void swap(int *a, int *b){
        int temp; 
        temp = *a; 
        *a = *b; 
        *b = temp; 
      }


      // Unsorted array is:   2  6  5  1 

      // Sorted array is:   2  6  5  1 

      // First partition: 
      // pivot = 1; 
      // 2,6,5,5
      // 2,6,6,5
      // 2,2,6,5
      // escape while loop
      // 1,2,6,5

 '

如果有人想看我的 Java 程序，就是这个:' 导入 java.util.Arrays;

    public class AltSorts {

     public static void QuickSort( double[] a, int L, int R ){
         int k;
         if ( R <= L){ 
             return;
            }   
         k = partition( a, L, R );

        QuickSort( a, L, k );   // Sort left half of partitioned array
        QuickSort( a, k+1, R); // Sort right half of partitioned array

    }

     public static int partition( double[] a, int L, int R )
     {
        double   pivot;
        double   help;
        int      S;
        int     B;
    /**
     [2     ,   6   ,   5   ,   1] 
      |                         |
      |                         |       once the two pointers cross we exist the while loop. 
      |                         |
      S                         B=4 & p[B]=1
     * */
        S = L;  //S = current Leftmost position
        B   = R-1;//B = rightmost position
        pivot = a[R-1];     //rightmost number in array

        while ( B > S )//as long as the two pointers don't cross you continue
        {
             if ( a[B -1] > pivot ){          //move to the right of the pivot 
              a[B] = a[B -1];
              B--;
         }
           else

           {  
               help = a[B -1]; // move to left of the pivot 
               a[B -1] = a[S];
               a[S] = help;
               S++;
           }
        }
        a[B] = pivot;   // Put pivot in the "hole" 
        return B; //return the position of the pivot
     }
     public static void main( String[] args )
     {
         double[] x = {2, 6, 5, 1}; 
        System.out.println("Before sort:    " + Arrays.toString(x) + "\n" );  

        QuickSort( x, 0, x.length );     // Quick sort

        System.out.println("\nAfter sort:     " + Arrays.toString(x) );
     }
    }

'

Answer 1

HuStmpHrrr指出了源代码中的一些问题。而且，多亏了他，我才能够弄清楚你做错了什么。

分区例程的结果不平衡(查看“pop”以及分区函数的返回值)

我根据您的实现编写了这段代码(做了一些更改)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

/// Function prototypes
void
swap( int *a, int *b );

void
quickSort( int *a, int low, int high );

int
partition( int *a, int low, int high );

int main( int argc, const char * argv[] ) {
    // insert code here...
    int a[] = { 2, 6, 5, 1 };

    quickSort( a, 0, 3 );

    for ( int i = 0; i < 4; ++i ) {
        printf( "%d ", a[ i ] );
    }

    return EXIT_SUCCESS;
}

/// Function definitions
void
swap( int *a, int *b )
{
    assert( a != NULL );
    assert( b != NULL );

    int temp = *a;
    *a       = *b;
    *b       = temp;
}

void
quickSort( int *a, int low, int high )
{
    assert( a != NULL );

    if ( high <= low ) {
        return;
    }

    int k = partition( a, low, high );
    quickSort( a, low, k - 1 );     /// Sort left part
    quickSort( a, k + 1, high );    /// Sort right part
}

int
partition( int *a, int low, int high )
{
    assert( a != NULL );

    bool flag  = false;
    int  first = low;        /// Left indice
    int  last  = high +1;    /// Right indice
    int  pivot = a[ low ];   /// Partitioning item

    while ( !flag ) {
        while ( a[ ++first ] < pivot ) {   /// Scan left and move
            if ( first == high) flag = true;
        }
        while ( a[ --last ] > pivot ) {    /// Scan right and move
            if ( last == low ) flag  = true;
        }

        if ( first >= last ) {
            flag = true;
        }
        else {
            swap( &a[ first], &a[ last ] );
        }
    }

    swap( &a[ low ], &a[ last ] );

    return last;
}