算法导论学习笔记--快速排序

[root@mip-123456 quick_sort]# cat quick.c
#include <stdio.h>

#define N 10

inline int exchange(int* a,int* b)
{
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;

  return 0;
}

int partition(int* A,int p ,int r)
{
  int tmp = 0;
  int i = 0;
  int j = 0;

  tmp = *(A+r);
  //printf("tmp is %d\n",tmp);

  i = p-1;
 
  for(j=p;j<r;j++)
   {
 // printf("A[%d] is %d\n",j,*(A+j));

     if(A[j]<tmp)
      {
         i++;
    // printf("before exchange %d %d\n",*(A+i),*(A+j));

            exchange(A+i,A+j);
     // printf("after exchange %d %d\n",*(A+i),*(A+j));

         }
     }
   exchange(A+i+1,A+r);
    
   return i+1;
}

int quick_sort(int* A,int p,int r)
{
  int q = 0;

 // printf("p = %d,r=%d\n",p,r);

 // printf("A[%d] = %d,A[%d] = %d\n",p,*(A+p),r,*(A+r));


  if(p<r)
    {
       q = partition(A,p,r);
       quick_sort(A,p,q-1);
       quick_sort(A,q+1,r);
    }

   return 0;
}

int main()
{
 int i = 0;
 int A[N] = {16,14,10,8,7,9,3,2,4,1};
 
 printf("before sort:\n");
 for(i=0;i<10;i++)
   printf("%5d",A[i]);

 quick_sort(A,0,N-1);
 printf("\nafter sort:\n");
 for(i=0;i<N;i++)
   printf("%5d",A[i]);
 printf("\n");
 return 0;
}
[root@mip-123456 quick_sort]# ./quick
before sort:
   16 14 10 8 7 9 3 2 4 1
after sort:
    1 2 3 4 7 8 9 10 14 16