快排两端排

  以前快排都是从头到尾那样排,进行了很多不必要的swap,两端排

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20

void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
       
void quicksort(int A[],int start, int end)
{
   if(start>=end)
     return;
     
   int p = start;
   int q = end;
   int x = A[end];
   
   while(p<q)
    {
      while(A[p]<x&&p<end)
       p++;
      while(A[q]>=x&&q>start)
       q--;
      
      if(p>q)
        break;
                
      swap(A+p,A+q);
    }
    swap(A+p,A+end);
    
   if(p<end)
     quicksort( A, p+1, end);
     
   if(q>start)
     quicksort( A, start, q );
}
  
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%30 + 1;
  
  printf("the original array is:\n");
  print_array(A);
    
  quicksort(A, 0, MAX_NUM-1);
  printf("after quick sort the array is:\n");
  print_array(A);
    
  system("PAUSE");    
  return 0;
}