Chinaunix

标题: 算法导论学习笔记--快速排序 [打印本页]

---

作者: ubuntuer    时间: 2009-05-18 14:00
标题: 算法导论学习笔记--快速排序

               
               
                [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;jr;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(pr)
    {
       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;i10;i++)
   printf("%5d",A);
quick_sort(A,0,N-1);
printf("\nafter sort:\n");
for(i=0;iN;i++)
   printf("%5d",A);
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


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_1932105.html

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2